算法提高课汇总

算法思路

理解题意

类似于多重背包问题: 物品$i$有$s_i + 1$种选择. 不同的是多重背包问题的选择是第$i$个物品选择
的个数, 而分组背包是第$i$组物品选择的种类.

$DP$分析

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

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

• 属性: Max物品价值

状态计算

对于状态$dp(i, j)$, 第$i$组物品的可选范围$k\in[0, s_i]$. 其中:

• $k = 0$, 表示不选第$i$组中任何物品

• $k\in [1, s_i]$, 表示选择第$i$组的第$k$个物品

为不失一般性, 假设第$i$组物品选择第$k$个:

• 确定部分: 选择物品$(i, k)$, 价值增加$w_{ik}$, 体积减少$v_{ik}. $($w_{i0} = v_{i0} = 0$)

• 剩余部分: 从前$i - 1$组选择, 且总体积不超过$j - v_{ik}$. 根据状态定义, 其对应集合的最大值为$dp(i - 1, j - v_{ik})$

状态的属性为Max: $dp(i, j) = max\lbrace dp(i - 1, j - v_{ik}) + w_{ik}\rbrace$, $k\in [0, s_i]$.

代码实现

空间朴素版本

#include <iostream>

using namespace std;

const int N = 110, M = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int dp[N][M];

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for( int j = 1; j <= s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

    for( int i = 1; i <= n; i ++ )
        for( int j = 0; j <= m; j ++ )
            for( int k = 0; k <= s[i]; k ++ ) //k = 0对应不选
                if( j >= v[i][k] )
                    dp[i][j] = max( dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k] );
    cout << dp[n][m] << endl;

    return 0;
}

空间优化版本

#include <iostream>

using namespace std;

const int N = 110, M = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int dp[M];

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for( int j = 1; j <= s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

    for( int i = 1; i <= n; i ++ )
        for( int j = m; j >= 0; j -- )
            for( int k = 1; k <= s[i]; k ++ ) //k = 0对应不选 优化后不需要考虑
                if( j >= v[i][k] )
                    dp[j] = max( dp[j], dp[j - v[i][k]] + w[i][k] );
    cout << dp[m] << endl;

    return 0;
}