【动态规划/多重背包问题】POJ1014-Dividing

多重背包问题的优化版来做，详见之前的动态规划读书笔记。

dp[i][j]表示前i中数加得到j时第i种数最多剩余几个（不能加和得到i的情况下为-1）递推式为：

dp[i][j]=mi(dp[i-1][j]≥0，即前i-1种数就能达到数字j)

　　　=-1(j<ai 或者 dp[i][j-ai]≤0，即再加上一个第i种数也无法达到j 或者当前和小于当前数)

　　　=dp[i][j-ai]-1(可以达到的情况)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int a[10];
 7 int dp[60000+10];
 8 
 9 int main()
10 {
11     int kase=0;
12     while (scanf("%d",&a[1]))
13     {
14         kase++;
15         int sum=a[1];
16         for (int i=2;i<=6;i++)
17         {
18             scanf("%d",&a[i]);
19             sum+=a[i]*i;
20         }
21         if (sum==0) break;
22         
23         
24         bool f=false;
25         if (sum%2==0)
26         {
27             sum=sum/2;
28             for (int i=1;i<=sum;i++) dp[i]=-1;
29             dp[0]=0;
30             for (int i=1;i<=6;i++)
31                 for (int j=0;j<=sum;j++)
32                 {
33                     if (dp[j]>=0) dp[j]=a[i];
34                     else
35                     {
36                         if (j<i || dp[j-i]<=0) dp[j]=-1;
37                             else dp[j]=dp[j-i]-1;
38                     }
39                 }
40             if (dp[sum]>=0) f=true;
41         }     
42         cout<<"Collection #"<<kase<<':'<<endl;
43         if (f) cout<<"Can be divided."<<endl;
44         else cout<<"Can't be divided."<<endl;
45         cout<<endl;
46     }
47 }