动态规划背包相关问题2-完全背包问题解析

上一篇文章介绍了01背包问题及分析，这篇短文主要介绍一个有点不同的题目：完全背包问题。具体题目内容如下：有N种物品和一个容量是V的背包，每种物品都有无限件可用。第 𝑖 种物品的体积是𝑣𝑖，价值是𝑤𝑖。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。其中输入格式和样例等和上一篇文章一样，具体可以参考引文1链接。

问题分析：和01背包不同的是，每一种物体可以放多个（具体个数上限为V/v[i]）,从另一个角度灵活考虑，可以认为该问题可以转换为01背包问题。及一种物体可以看成是V/v[i]种不同的物体，但其价值相同。通过这样转换后完全背包问题就可以转化为01背包问题。转换的代码如下所示。其中dp_solver的递推计算和01背包中国的代码段是一样的。

    cin >> N >> V;
    int* v_;
    int* w_;
    v_ = (int*)malloc((N+1)*sizeof(int));
    w_ = (int*)malloc((N+1)*sizeof(int));
    int* count = (int*)malloc((N+1)*sizeof(int));
    int total_count = 0;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> v_[i] >> w_[i];
        count[i] = V/v_[i];
        total_count += count[i];
    }
    v = (int*)malloc((total_count+1)*sizeof(int));
    w = (int*)malloc((total_count+1)*sizeof(int));
    int N_ = 1;
    for(int i = 1; i <= N; i++)
    {
        for(int k = 0; k < count[i]; k++)
        {
            v[N_] = v_[i];
            w[N_] = w_[i];
            N_++;
            
        }
    }
    N = N_--;
    dp= (int**)malloc((N+1)*sizeof(int*));
    for(int i = 0; i < N+1; i++)
    {
        dp[i] = (int*)malloc((V+1)*sizeof(int));
    }

下面的思路提供一种更简洁的实现，具体的状态转移方程有一定的变化，即当j>v[i]的时候，可以放入1到j/v[i]个物体，因此状态转移方程写为：

dp[i][j] = max(dp[i-1][j-m*v[i]]+m*w[i], dp[i-1][j])（其中m=1,2,…j/v[i]）

具体代码如下(dp[1][j]的定义也有变化)：

int dp_solver()
{
    for(int i = 1; i < N+1; i++)
    {
        for(int j = 1; j < V+1; j++){
            if(j >= v[i] && i==1)
            {
                dp[i][j] = w[i]*(int)(j/v[i]);
            }else if(j < v[i] && i==1){
                dp[i][j] = 0;
            }
            else if(i > 1 && j >= v[i]){
                int k = int(j/v[i]);
                for(int m=1; m <= k; m++)
                {
                    dp[i][j] = std::max(dp[i-1][j-m*v[i]]+m*w[i], dp[i-1][j]);
                }
            }else if(i > 1 && j < v[i])
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][V];    
}

int main()
{
    cin >> N >> V;
    v = (int*)malloc((N+1)*sizeof(int));
    w = (int*)malloc((N+1)*sizeof(int));
    dp= (int**)malloc((N+1)*sizeof(int*));
    for(int i = 0; i < N+1; i++)
    {
        dp[i] = (int*)malloc((V+1)*sizeof(int));
        //下面这段代码再用dfs相关的函数中调用
        // for(int j=0; j < V+1; j++)
        // {
        //     dp[i][j] = -1;
        // }
    }
    for(int i =1; i <= N; i++)
    {
        //scanf("%d %d\n", &v[i], &w[i]);
        cin >> v[i] >> w[i];
        //cout << v[i] << w[i] << std::endl;
    }
    //int val = dfs_with_cache(1, V);
    //cout << val;
    dp_solver();
}

References

• 1、动态规划背包相关问题1-整数背包问题解析