分组背包

出自《背包九讲》

问题

有$N$件物品和一个容量为$V$的背包。第$i$件物品的体积是$c_i$,价值是$w_i$。这些
物品被划分为$K$组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包
可使这些物品的体积总和不超过背包容量,且价值总和最大。

思想

$dp[i][j]$:表示前i组,容量为j,的最大价值

那么对于每组来说,就有选一件或者不选两种决策。

时间复杂度$O(VN)$

1
2
3
4
5
for k = 1 : K
for j = V : 0
for item in k
if(j >= c[item])
dp[j] = max(dp[j], dp[j - c[item]] + w[item]);

Thank you for your support!