背包问题的动态规划解法 描述 背包问题是一个经典的组合优化问题，常见于面试和实际应用中。问题描述为：给定一组物品，每个物品有重量（weight）和价值（value），以及一个容量为C的背包。目标是从物品中选择一些放入背包，使得总重量不超过C，且总价值最大。背包问题分为0-1背包（每个物品最多选一次）和完全背包（每个物品可选无限次），这里我们聚焦于0-1背包的动态规划解法。 解题过程 动态规划通过将问题分解为子问题来避免重复计算。对于0-1背包，核心思路是逐个考虑物品和容量，构建一个二维DP表。 定义状态 设 dp[i][j] 表示考虑前 i 个物品（物品编号从1到i），在背包容量为 j 时能获得的最大价值。 其中 i 的范围是0到n（n为物品总数）， j 的范围是0到C（C为背包总容量）。 初始化基础情况 当物品数量为0（i=0）时，无论容量多大，最大价值均为0： dp[0][j] = 0 （j从0到C）。 当背包容量为0（j=0）时，无论有多少物品，最大价值均为0： dp[i][0] = 0 （i从0到n）。 状态转移方程 对于每个物品i和容量j，分两种情况： 不选第i个物品 ：最大价值等于前i-1个物品在容量j下的结果，即 dp[i][j] = dp[i-1][j] 。 选第i个物品 （前提是当前容量j ≥ 物品i的重量w_ i）：最大价值为物品i的价值v_ i加上前i-1个物品在剩余容量 j - w_i 下的结果，即 dp[i][j] = v_i + dp[i-1][j - w_i] 。 最终取两种情况的最大值： dp[i][j] = max(dp[i-1][j], v_i + dp[i-1][j - w_i]) （若j ≥ w_ i，否则只能不选）。 填表顺序 外层循环遍历物品i从1到n，内层循环遍历容量j从1到C。确保计算 dp[i][j] 时， dp[i-1][j] 和 dp[i-1][j - w_i] 已计算。 获取最终结果 最大价值存储在 dp[n][C] 中。若需知道具体选了哪些物品，可通过反向追踪DP表：从 dp[n][C] 开始，若 dp[i][j] != dp[i-1][j] ，说明选了物品i，然后跳转到 dp[i-1][j - w_i] 继续追踪。 示例 假设物品列表：重量w = [ 2, 3, 4, 5]，价值v = [ 3, 4, 5, 6 ]，容量C=8。 建表：行i从0到4（4个物品），列j从0到8。 填表后， dp[4][8] = 10 （选物品2和4，重量3+5=8，价值4+6=10）。 优化 空间优化：由于 dp[i] 只依赖 dp[i-1] ，可改用一维数组 dp[j] ，内层j需从C到w_ i逆序遍历，避免覆盖前一状态。