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