四要素分析:
状态:dp[i][j] 表示前 i 种物品、容量 j 的最大价值(二维状态覆盖“物品种类”和“背包容量”)。
转移:对第 i 种物品,枚举选择次数 k(0≤k≤min(k[i], j/w[i])),则 dp[i][j] = max(dp[i][j], dp[i-1][j - kw[i]] + kv[i])(遍历所有合法选择次数,取最大价值)。
边界:dp[0][j] = 0(前0种物品,价值为0)、dp[i][0] = 0(容量为0,价值为0)。
答案:dp[n][m](前 n 种物品、容量 m 的最大价值)。
二进制优化版(拆分为01背包):
四要素分析:
状态:dp2[j] 表示容量 j 的最大价值(压缩为一维,通过二进制拆分将“有限次选择”转为“01背包单次选择”)。
转移:
若 k[i]*w[i] ≥ m(物品数量足够多,等价于完全背包):正向遍历 j = w[i] ~ m,dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i]);
若 k[i]*w[i] < m(物品数量有限,二进制拆分):将 k[i] 拆分为 2^0, 2^1,..., 剩余值,每组视为“01背包的单件物品”,反向遍历 j = m ~ 组重量,dp2[j] = max(dp2[j], dp2[j - 组重量] + 组价值)。
边界:dp2[j] = 0(初始所有容量的价值为0)。
答案:dp2[m](容量 m 的最大价值)。