ACM_01背包（恰好装满）

背包2

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

有n个重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量刚好为 W 的物品，求所有方案中价值总和的最大值。

Input:

输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000），接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）。

Output:

输出为一行，即所有方案中价值总和的最大值。若不存在刚好填满的情况，输出“-1”。

Sample Input:

3 4
1 2
2 5
2 1
3 4
1 2
2 5
5 1

Sample Output:

6
-1
解题思路：求01背包恰好装满时得到的最大价值，应该这样初始化：①dp[0]=0，表示背包容量为0时得到的最大价值也为0；②dp[1～W]=-inf，表示背包容量为其他状态下都为非法状态（未装满），因为我们还要求解恰好装满的情况下得到的最大价值。那么在求解过程中，由于动规的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，所以如果子问题状态是非法的(-inf)，则当前问题的状态依然非法，即不存在恰好装满的情况；相反，如果子问题的状态是合法(不是-inf)的（恰好装满），那么当前问题求解也可得到合法状态。这样最后判断一下dp[W]是否恰好装满即dp[W]>=0，否则为未装满状态。
AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,W,w[10005],v[10005],dp[1005];
int main(){
    while(cin>>n>>W){
        memset(dp,-0x3f,sizeof(dp));dp[0]=0;
        for(int i=1;i<=n;++i)
            cin>>w[i]>>v[i];
        for(int i=1;i<=n;++i)
            for(int j=W;j>=w[i];--j)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        if(dp[W]<0)cout<<-1<<endl;
        else cout<<dp[W]<<endl;
    }
    return 0;
}