关于 分组背包

问题描述：

有 N 种物品和一个容量为 V 的背包，每组物品有若干个，同一组内的物品最多只能选一个。每件体积是 w[i][j] ，价值是 v[i][j] 。求解将哪些物品装入背包可使价值总和最大。

问题特点：

每组有至少一个不同的物品，每组最多选一个（可以不选）。

与多重背包的关系：

分组背包在面对一组内 s 个的物品时，共有 s+1 种决策情况，分别是选第 0,1,2...s 个物品（选第 0 个物品即不选该组内任何物品）。多重背包中每个物品有 s 个，也有 s + 1 种决策情况，分别是选 0,1,2...s 个该物品，在此可以和上面的情况做一下对比区分。多重背包可以说是分组背包的一个特殊情况，所以多重背包可以用放弃数组完整性的代价来优化算法。

模板：

for(int i = 1; i <= n; i ++)
        for(int j = m; j >= 0; j --)
            for(int k = 0; k <= s[i]; k ++)
                if(v[i][k] <= j)
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);

模板题：9. 分组背包问题 - AcWing题库