子集和是一个很著名的问题, html
一个集合S{s1,s2,s3,s3,...,sn}, 给一个数s,问是否存在一个S的一个或多个子集,使得该子集内全部元素的和等于给出的数.java
显然利用一个辅助的数字x[],能够在O(2^n)时间复杂度内完成搜索出全部的解.数组
当若是要问存在多少个子集可以组成目标数字. 咱们能够利用动态规划的方法来获得答案, 这样时间和空间复杂度是O(s*n), s是目标数字, n是备选集合的元素个数.post
动态方程是: 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的子集个数.spa
----code
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); } }
-----htm
这两天看topcoder上SRM 548 div1的第二题, 想到了另一个子集和相关的问题. 就是:blog
在组成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);
}
}