Onway

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