算法提高课汇总

题意理解

回忆3中背包问题 的$DP$分析: 唯一不同的是状态表示: (实际上是不同背包物品$i$可选数目的范围).

$DP$分析

状态表示 $dp(i, j)$

• 集合: 从前$i$个物品中选, 且总体积不超过$j$的所有方案

• 属性: Max物品价值

状态计算

• $01$背包: $dp(i, j) = max\lbrace dp(i - 1, j), dp(i - 1, j - v_i) + w_i\rbrace$

• 完全背包: $dp(i, j) = max\lbrace dp(i - 1, j), dp(i, j - v_i) + w_i\rbrace$

• 多重背包: $dp(i, j) = max\lbrace dp(i - 1, j - k\times v_i) + k\times w_i\rbrace, k\in [0,min(\lfloor \frac{j}{v_i}\rfloor, s_i)]$

在分析状态$dp(i, j)$的过程中, 我们划分的依据是第$i$个物品选择的个数$k$, 划分后剩余的部分为
从前$i - 1$个物品中选且总体积不超过$j - k\times v_i$的集合. 在这个过程中对前$i - 1$个物品
的类型没有做出假设, 所以在本题的计算过程中, 每次只需关注物品$i$的类型按对应方式计算其状态.

代码实现

注意如果多重背包计算过程中不使用优化, 考虑极端情况: 所有背包都是多重背包, 那么时间复杂度为
$O(N\times V\times S)$, 超时. 另一方面为实现简单, 可以只做二进制优化. 优化后极端情况的时间复杂度为
$O(N\times V\times \lg{S})$.

$01$背包可以看作多重背包$s_i = 1$的特殊情况.

具体代码:

#include <iostream>

using namespace std;

const int M = 1010;

int n, m;
int dp[M];

int main()
{
    cin >> n >> m;

    for( int i = 1; i <= n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        if( !s )
        {//完全背包, 计算i的计算
            for( int j = v; j <= m; j ++ )  dp[j] = max( dp[j], dp[j - v] + w );
        }
        else
        {
            if( s == -1 )   s = 1; //01背包作为多重背包的一种特殊情况
            for( int k = 1; k <= s; k *= 2 )
            {
                //01背包的计算过程
                for( int j = m; j >= k * v; j -- )  dp[j] = max( dp[j], dp[j - k * v] + k * w );
                s -= k;
            }
            if( s )
            {
                for( int j = m; j >= s * v; j -- )  dp[j] = max( dp[j], dp[j - s * v] + s * w );
            }
        }
    }
    cout << dp[m] << endl;

    return 0;
}