子集和是一个很著名的问题, 

一个集合S{s1,s2,s3,s3,...,sn}, 给一个数s,问是否存在一个S的一个或多个子集,使得该子集内所有元素的和等于给出的数.

显然利用一个辅助的数字x[],可以在O(2^n)时间复杂度内完成搜索出所有的解.

当如果要问存在多少个子集能够组成目标数字. 我们可以利用动态规划的方法来得到答案, 这样时间和空间复杂度是O(s*n), s是目标数字, n是备选集合的元素个数.

动态方程是: f(i, j) =f(i-1, j) + f(i-1, j-S[i-1]) + (j==S[i]). 其中i从1到n, j从1到s.

最终结果f(n,s)就是可以组成s的子集个数.

----

import java.util.Arrays;public class SumOfSub {    int num=0;    public void solve(int a[], int s, int x[], int i){        if(i==x.length){            return;        }        x[i]=1;        int sum=0;        int j;        for(j=0;j<=i;j++){            sum+=a[j]*x[j];        }        if(sum==s){            System.out.println("Find Solution "+num+" "+Arrays.toString(x));            num++;        }        solve(a,s,x,i+1);        x[i]=0;        solve(a,s,x,i+1);    }    public void solveUsingDp(int a[], int s){        int n=a.length;        int c[][]=new int[n+1][s+1];        for(int i=1;i<=n;i++){            for(int j=1;j<=s;j++){                if(j>=a[i-1]){                    c[i][j]=c[i-1][j]+c[i-1][j-a[i-1]];                    if(j==a[i-1]){                        c[i][j]+=1;                    }                }                else                     c[i][j]=c[i-1][j];            }        }        System.out.println("Total Solution num: "+c[n][s]);    }    public static void main(String args[]){        SumOfSub ss=new SumOfSub();        int a[]=new int[]{3,5,8,2,7,1,6};        int s=14;        int x[]=new int[7];        ss.solve(a, s, x, 0);        System.out.println(ss.num);        ss.solveUsingDp(a, s);    }}

 

-----

 

这两天看topcoder上SRM 548 div1的第二题, 想到了另外一个子集和相关的问题. 就是:

在组成s的所有子集中, 元素个数最少的那个子集所含元素个数是什么?

当然, 利用第一种搜索的方式可以的得到答案, 但时间复杂度太高. 如果n稍微大一些, 则搜索过程会很漫长. 有没有更好的方法呢?

tc网站上给出了一种很好的方法, 两重循环就可以搞定.

具体来说就是 先将S集合升序排序, 然后利用一个cnt[]数组, 数组长度为s, cnt[i]意思为表示数字i的所有子集的元素个数最小的那个的元素个数.cnt[0]=0. 

初始化cnt[1]~cnt[n-1]=n+1;

 for(i=0;i<S.length; i++){

for(j=1;j<=s;j++){

if(j>=S[i]) cnt[j]=min(cnt[j], cnt[j-S[i]]+1);

}

}