ACM_完全背包

背包3

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:

输出为一行，即所有方案中价值总和的最大值。

Sample Input:

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

Sample Output:

10
7
解题思路：简单的完全背包。和01背包一样，dp[i][j]表示从前i种物品中挑选总重量不超过j时总价值的最大值。
易得状态转移方程：dp[i,j]=max(dp[i-1,j-k*wi]+k*vi)（0<=k*wi<=W），其中dp[i-1,j-k*wi]+k*vi表示前i-1种物品中选取若干件物品放入剩余容量为j-k*wi的背包中所能得到的最大价值加上k件第i种物品。很明显，多了一个参数k，时间复杂度变为O(nW∑(W/wi))，可知这样的时间复杂度是很大的，我们必须找到更优的办法。
因为在dp[i,j]的计算中选择k(k>=1)个物品得到的最大价值与在dp[i][j-wi](背包中已包含至少一件第i种物品)的计算中选择k-1个物品得到的最大价值是相同的，所以dp[i][j]的递推中k>=1部分的计算已经在dp[i][j-wi]的计算中完成了。那么有如下推导过程：
dp[i,j-wi]=max(dp[i-1,j],dp[i-1,(j-wi)-(k-1)*wi]+(k-1)*vi)(k>=1,dp[i-1,j]表示第i种物品一件都不选)
          =max(dp[i-1,j],dp[i-1,j-k*wi]+(k-1)*vi)(k>=1,表示当前背包中至少含有一件第i种物品)
dp[i,j]=max(dp[i-1,j],dp[i-1,j-k*wi]+k*vi)(k>=1)
　 　　=max(dp[i-1,j],dp[i,j-wi]+vi)
于是成功地把参数k给消掉了，现在的时间复杂度和01背包一样都为O(nW)。
怎么理解上面的状态转移方程呢？①如果第i件物品一件都不取，显然dp[i,j]=dp[i-1,j]；②如果要取，那么当前背包中至少已含有一件第i种物品(即j至少已含有一个wi)，则dp[i,j]=dp[i,j-wi]+vi。因为01背包中每个物品只有一件，在放入第i件物品时需考虑到前i-1件物品放入剩余背包容量为j-wi得到的最大价值，但是现在每个物品拥有无限件，即无需考虑前i-1个物品了，所要考虑的就是当前容量下能否再放入一件第i种物品，而dp[i,j-wi]已确保dp[i,j]中至少有一件第i种物品，所以要预留wi的背包容量再来存放一件第i种物品，这样就实现了一个物品可以取多件的操作。
同样地，完全背包空间也可以优化到O(W)。怎么实现呢？只需将01背包第二重循环正序枚举即可。为什么呢？通过模拟过程可以发现，正序使得一个物品可以被取多次。因为01背包中按照W递减来循环是为了保证第i次循环中的状态dp[i,j]是由状态dp[i-1,j-wi]递推而来，换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果dp[i−1,j−wi]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果dp[i,j-wi],所以就可以并且必须采用wi～W递增的顺序循环。
一维滚动数组状态转移方程：dp[j]=max(dp[j],dp[j-w[i]]+v[i])。
AC代码一：（二维数组实现）

#include<bits/stdc++.h>
using namespace std;
int n,W,v[10005],w[10005],dp[1005][1005];
int main(){
    while(cin>>n>>W){
        for(int i=1;i<=n;++i)cin>>w[i]>>v[i];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i){
            for(int j=0;j<=W;++j){
                if(j<w[i])dp[i][j]=dp[i-1][j];//当前容量j容纳不下一件第i种物品
                else dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);//再拿一件第i种物品和一件都不拿的情况比一下
            }
        }
        cout<<dp[n][W]<<endl;
    }
    return 0;
}

AC代码二：（一维数组实现）

#include<bits/stdc++.h>
using namespace std;
int n,W,v[10005],w[10005],dp[1005];
int main(){
    while(cin>>n>>W){
        for(int i=0;i<n;i++)
            cin>>w[i]>>v[i];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;++i)   //种类
            for(int j=w[i];j<=W;++j) //重量从小到大枚举
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        cout<<dp[W]<<endl;
    }
    return 0;
}