HDU 2159 FATE

http://acm.hdu.edu.cn/showproblem.php?pid=2159

二维的背包问题....

个人感觉是0/1背包和完全背包的结合.

View Code

 1 #include <iostream>
 2 using namespace std;
 3 const int maxn=101;
 4 int ans[maxn][maxn],v[maxn],w[maxn];
 5 int main()
 6 {
 7     int n,m,k,s,i,j,l,max;
 8     while(cin>>n>>m>>k>>s)
 9     {
10         max=-1;
11         for(i=0;i<k;i++)
12         cin>>w[i]>>v[i];
13         for(i=0;i<=s;i++)
14         for(j=0;j<=m;j++)
15         ans[i][j]=0;
16         for(i=0;i<k;i++)
17         {
18             
19             for(l=0;l<=m;l++) //两个循环的位置必须注意
20             for(j=s;j>=0;j--)
21             {
22                 if(j-1>=0 && l>=v[i] && ans[j-1][l-v[i]]+w[i]>ans[j][l])
23                     ans[j][l]=ans[j-1][l-v[i]]+w[i];
24                 if(ans[j][l]>=n && m-l>max)
25                     max=m-l;
26             }
27         }
28         printf("%d\n",max);
29     }
30     return 0;
31 }

刚开始因为 v[], w[]的的输入搞错了....一直在WA