动态规划——完全背包问题

完全背包问题一般是指：

有N件物品和一个能背重量为W的背包，第i件物品的重量为weight[i],价值为value[i]。每件物品有无限个(也就是可以放入背包多次），求怎样可以使背包物品价值总量最大。

完全背包与01背包问题的区别在于01背包物品只有一个，完全背包有无数个。

1、原始朴素算法：

dp[i][j] 的状态表示：①集合：表示前i个物品中，总体积不超过j的选法的物品价值最大值    ②属性：当前情况下的最大值

dp[i][j] 的状态计算：当前的第i个物品，可以选任意多个（总体积不超过背包容量）。那么就枚举呗，从选0个到选k个枚举，dp[i][j]=max(dp[i-1][j]，dp[i-1][j-weight[i]]+value[i]，dp[i-1][j-2*weight[i]]+2*value[i]，......，dp[i-1][j-k*weight[i]]+k*value[i])    (※)

朴素代码：

#include<iostream>
using namespace std;
int main(){
    int n,cap;
    cin>>n>>cap;
    int *v=new int[n];
    int *w=new int[n];
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    int **dp=new int*[n+1];
    for(int i=0;i<=n;i++){
        dp[i]=new int[cap+1];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cap;j++){
            for(int k=0;k*v[i-1]<=j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i-1]]+k*w[i-1]);
            }
        }
    }
    cout<<dp[n][cap];
    return 0;
}

朴素算法有三重循环，我们现在将其优化成二重循环，原理如下：

上面的(※)式：dp[i][j]=max(dp[i-1][j]，dp[i-1][j-weight[i]]+value[i]，dp[i-1][j-2*weight[i]]+2*value[i]，......，dp[i-1][j-k*weight[i]]+k*value[i])

则dp[i][j-weight[i]]可按此公式推得(※1)：dp[i][j-weight[i]]=max(dp[i-1][j-weight[i]]，dp[i-1][j-2*weight[i]]+value[i]，dp[i-1][j-3*weight[i]]+2*value[i]，......，dp[i-1][j-k*weight[i]]+(k-1)*value[i])

可以观察到，(※)的加粗部分和(※1)的加粗部分大致相同，只是(※)的加粗部分每项多加一个value[i]（每项都加，等于没加，最大值还是那一项，只是值不同），也就是说(※1)的最大值比(※)的最大值多了一个value[i]。

那么便可以把(※1)带入(※)中，让表达式更加简洁一些，(※)改进得：

dp[i][j]=max(dp[i-1][j]，dp[i][j-weight[i]]+value[i])   （核心）

2、优化成双层循环的算法：

#include<iostream>
using namespace std;
int main(){
    int n,cap;
    cin>>n>>cap;
    int *v=new int[n];
    int *w=new int[n];
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    int **dp=new int*[n+1];
    for(int i=0;i<=n;i++){
        dp[i]=new int[cap+1];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cap;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=v[i-1])dp[i][j]=max(dp[i][j],dp[i][j-v[i-1]]+w[i-1]);
        }
    }
    cout<<dp[n][cap];
    return 0;
}

3、继续优化成一维dp数组的算法：

#include<iostream>
using namespace std;
int main(){
    int n,cap;
    cin>>n>>cap;
    int *v=new int[n];
    int *w=new int[n];
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    int *dp=new int[cap+1];
    for(int i=1;i<=n;i++){
        for(int j=v[i-1];j<=cap;j++){
            dp[j]=max(dp[j],dp[j-v[i-1]]+w[i-1]);
        }
    }
    cout<<dp[cap];
    return 0;
}

 4、小结：

优化成一维的与01背包的状态转移方程对比，仅仅微小的区别，但是背后含义千差万别：

01背包：dp[i][j]= max(dp[i-1][j]，dp[i-1][j-w]+v)

完全背包：dp[i][j]=max(dp[i-1][j]，dp[i][j-w]+v)

这个微小的区别，导致了一维空间时，01背包是从后向前遍历（防止左边的数，即含义上是上一层的数被修改覆盖），完全背包是从前向后遍历（需要这一层前面的数）。