问题
有 n 组物品,其中第 i 组有 c[i] 个物品。第 i 组的第 j 个物品体积为 v[i][j] 价值为w[i][j]。
有一组容积为 m 的背包,每组最多选一个物品装入背包,求解将哪些物品装入背包可使这些物品的总体
积不超过背包容量,且价值总和最大。
时间复杂度
n
O( ∑ ( c[i] ) * m )
i = 1
状态表示
f[i][j]表示前 i 件物品放入一个容量为 j 的背包可以获得的最大价值
状态转移方程
f[i][j] = max( f[i - 1][j], max{ f[i - 1][j - v[i][k]] + w[i][k] } )
k∈[1 ~ c[i]]
初值
f[0 ~ n][0 ~ m] = 0
目标
f[n][m]
code
for( int i = 1; i <= n; i ++ )
for( int j = m; j >= 0; j -- ) 倒序
for( int k = 1; k <= c[i]; k ++ )
if( j >= v[i][k] )
f[j] = max( f[j], f[j - v[i][k]] + w[i][k] );