又见01背包

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 int dp[10001];
 6 int v[105],w[105];
 7 int main()
 8 {
 9     int n,W,i,j,sum;
10     while(~scanf("%d%d",&n,&W))
11     {
12         sum=0;
13         for(int i=1;i<=n;i++)
14         {
15             scanf("%d%d",w+i,v+i);
16             sum+=v[i];
17         }
18         for(i=1;i<=sum;i++) dp[i]=1<<30;
19         dp[0]=0;
20         for(i=1;i<=n;i++)
21             for(j=sum;j>=v[i];j--)
22                 dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
23         for(i=sum;i>=0;i--)
24             if(dp[i]<=W)
25         {
26             printf("%d
",i);
27             break;
28         }
29     }
30     return 0;
31 }

View Code

感觉这题像是把递归的程序写成非递归的程序，写dp的程序太少，以后多练吧！

dp[i]代表i价值的最小重量.