二维优化版
四要素分析
状态:dp[i][j] 表示前 i 种物品、容量 j 的最大价值(与暴力版一致)。
转移:
若 j < w[i](容量不足,无法选第 i 种物品),则 dp[i][j] = dp[i-1][j](继承前 i-1 种物品的状态);
若 j ≥ w[i](容量足够,可重复选第 i 种物品),则 dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])(dp[i][j - w[i]] 已包含第 i 种物品的多次选择,无需枚举 k)。
边界:dp[0][j] = 0、dp[i][0] = 0(与暴力版一致)。
答案:dp[n][m](与暴力版一致)。
一维优化版(正向迭代):
四要素分析:
状态:dp2[j] 表示容量 j 的最大价值(压缩为一维,通过迭代顺序保证“物品可重复选”)。
转移:对每种物品 i,正向遍历容量 j = w[i] ~ m,则 dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i])(正向迭代允许 dp2[j - w[i]] 已包含当前物品的选择记录,实现重复选)。
边界:dp2[j] = 0(初始所有容量的价值为0,无物品时价值为0)。
答案:dp2[m](容量 m 的最大价值)。