Chinaunix

标题: 01背包问题--划分成两个子集合，且保证每个集合的数字和是相等 [打印本页]

---

作者: kaede_1    时间: 2014-11-06 16:18
标题: 01背包问题--划分成两个子集合，且保证每个集合的数字和是相等
对于从 1 到 N 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等

1. #include<iostream>
   
2. #include<malloc.h>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7. int dyn[100];
   
8. memset(dyn,0,100);
   
9. int n,s;
   
10. cin>>n;
    
11. s=n*(n+1);
    
12. if(s%4)
    
13. {
    
14.   cout<<0<<endl;
    
15. }
    
16. s/=4;
    
17. int i,j;
    
18. dyn[0]=1;
    
19. for(i=1;i<=n;i++)//表示这个次选取的是数为i
    
20. {
    
21.   for(j=s;j>=i;j--)
    
22.    [color=Red]dyn[j]+=dyn[j-i];[/color]//dyn[j-i]表示加起来等于j-i的组数，
    
23. }                        //dyn[j]表示加起来等于j的组数
    
24. cout<<dyn[s]/2<<endl;//由于交换两个子集合的位置被认为是同一种划分方案，所以最终结果为dyn[s]/2
    
25. return 1;
    
26. }

复制代码

标红一句有点没看明白，哪位帮忙提示一下，多谢！

---

作者: 雷男    时间: 2015-01-19 20:05
通过递归的方法遍历出所有的dyn[x],x from 1 to s。

标红的意思是，算出从和为i到s各种组合中带i的次数。这里我总觉得会重复很多次。

楼主你这代码哪里来的，memset都搞错了

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2