完全背包

题意 : 有无数件可以用的物品 , 但是背包必须装满

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<iostream>
 5 #include<limits.h>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 #include<stack>
11 #include<string>
12 #include<sstream>
13 #include<map>
14 #include<cctype>
15 using namespace std;
16 int main()
17 {
18     int t,w[2005],v[2005],V,n,dp[50005];
19     scanf("%d",&t);
20     while(t--)
21     {
22         scanf("%d%d",&n,&V);
23         memset(v,0,sizeof(v));
24         for(int i=0;i<n;i++)
25             scanf("%d%d",&w[i],&v[i]);
26         dp[0]=0;
27         for(int i=1;i<50005;i++)
28             dp[i]=INT_MIN/10;
29         for(int i=0;i<n;i++)
30         {
31             for(int j=V;j>=w[i];j--)
32             {
33                 dp[j]=dp[j]>dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];
34             }
35         }
36         if(dp[V]<0)
37             printf("No
");
38         else
39             printf("%d
",dp[V]);
40     }
41     return 0;
42 }