hdu

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

f[v][u]=max(f[v][u],f[v-1][u-w[i]]+v[i];

注意中间一层必须逆序循环.

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 int dp[21][1001];
 6 int v[1001],w[1001];
 7 int main()
 8 {
 9     //freopen("a.txt","r",stdin);
10     int t,n,m,k;
11     scanf("%d",&t);
12     while(t--)
13     {
14         scanf("%d%d",&n,&k);
15         for(int i=1;i<=n;i++)
16         {
17             scanf("%d%d",&v[i],&w[i]);
18         }
19         scanf("%d",&m);
20         memset(dp,0,sizeof(dp));
21         for(int i=1;i<=n;i++)
22         {
23             for(int l=k;l>=1;l--)
24             for(int j=m;j>=w[i];j--)
25             dp[l][j]=max(dp[l][j],dp[l-1][j-w[i]]+v[i]);
26         }
27         printf("%d
",dp[k][m]);
28     }
29     return 0;
30 }