又见01背包

又见01背包

4 52 31 23 42 2样例输出
7
#include <bits/stdc++.h>using namespace std;const int maxn = 105;int dp[10005];struct res{	int vi,wi;//vi是单位重量的价值，wi是重量}arr[maxn];int main(){	int n,sum,w;//有n组测试数据，背包内能装物品的最大价值和为sum	while(~scanf("%d%d",&n,&w))    {        sum=0;        for(int i=0;i<n;i++)        {            cin>>arr[i].wi>>arr[i].vi;            sum +=arr[i].vi;        }         memset(dp,100,sizeof(dp));         dp[0] = 0;        for( int i = n-1 ;i>=0 ;i--)        for( int j = sum;j>=arr[i].vi ;j--)  //  j〉=vi[i] ，注意        {            dp[j] = min(dp[j] ,dp[j-arr[i].vi]+arr[i].wi);        }        int i;        for(i = sum;i>=0;)         if(w>= dp[i])            break;         else i--;         PRintf("%d/n",i);    }    return 0;}