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[],v[],dp[];

 int main(){

     while(cin>>n>>W){

         memset(dp,-0x3f,sizeof(dp));dp[]=;

         for(int i=;i<=n;++i)

             cin>>w[i]>>v[i];

         for(int i=;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]<)cout<<-<<endl;

         else cout<<dp[W]<<endl;

     }

     return ;

 }