Onway

我是一只菜菜菜菜鸟...
posts - 61, comments - 56, trackbacks - 0, articles - 34

pku 1014 Dividing 多重背包

Posted on 2010-08-04 23:26 Onway 阅读(273) 评论(0)  编辑 收藏 引用 所属分类: 伤不起的ACM

pku 1014 Dividing

这个题目跟3211 Washing Clothes做法非常相似，虽然3211是0-1背包，1014是多重背包。思路都是将总价值的一半作为背包容量，然后进行背包策略就行了。

用多重背包的个数标记，时间为O(N*M),一次AC。

然后用二进制物品压缩，数组开小了，居然报WA，晕死。

 1#include <iostream>
 2using namespace std;
 3const int MAX=60000;
 4bool sgn[MAX+1];
 5int cnt[MAX+1];
 6int data[7];
 7int main()
 8{
 9    int cas=0;
10    while(cin>>data[1]>>data[2]>>data[3]>>data[4]>>
11        data[5]>>data[6])
12    {
13        int i,j,n=6,sum=0;
14        for(i=1;i<=n;++i)
15            if(data[i]!=0)
16                break;
17        if(i>n)        break;
18
19        ++cas;
20
21        memset(sgn,0,sizeof(sgn));
22        sgn[0]=1;
23        for(i=1;i<=n;++i)
24        {
25            memset(cnt,0,sizeof(cnt));
26            for(j=i;j<=MAX;++j)
27                if(!sgn[j]&&sgn[j-i]&&cnt[j-i]<data[i])
28                {
29                    cnt[j]=cnt[j-i]+1;
30                    sgn[j]=1;
31                }
32        }
33        
34        for(i=1;i<=n;++i)
35            sum+=data[i]*i;
36        if(sum%2||!sgn[sum/2])
37        {
38            cout<<"Collection #"<<cas<<":"<<endl;
39            cout<<"Can't be divided."<<endl;
40            cout<<endl;
41        }
42        else
43        {
44            cout<<"Collection #"<<cas<<":"<<endl;
45            cout<<"Can be divided."<<endl;
46            cout<<endl;
47        }
48    }
49    return 0;
50}
51

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理