题意:
给定一个集合,求不能由该集合子集拼出的最小数。
样例:
{2,5,1}
1,2,3均可以拼出,4不能拼出,故答案是4.
思路:
先把集合元素从小到大排序,首先,假设第1个数必须是1,否则答案就是1.
归纳法假证:
x=1时可以拼出1.(第1项满足)
对于任意x(x>=2),令s=Σ a(i), i∈[1,x-1] ,如果1~a(i)-1均能拼出(即s>=a(i)-1),加一个a(i)可以拼出1~s+a(i).
因此:方法就是找第一个a(x),满足s=Σ a(i), i∈[1,x-1],满足s<=a(i)-2.这时s+1就是答案。
这个思路类似于多重背包的二进制拆分