问题 有 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] );