动态规划巧解背包问题：7 个物品 150 容量，算出 170 总价值！

### 背包问题解决方案 给定的背包问题可以通过动态规划来解决。这里我们用一个二维数组 `dp` 来存储在不同背包容量下，前 `i` 个物品的最大价值。 #### 代码实现 ```python def knapsack(n, weights, values, capacity): # 初始化 dp 数组，dp[i][j] 表示前 i 个物品在容量为 j 的背包中的最大价值 dp = [[0] * (capacity + 1) for _ in range(n + 1)] # 填充 dp 数组 for i in range(1, n + 1): for w in range(1, capacity + 1): if weights[i - 1] <= w: # 如果当前物品可以放入背包 dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) else: # 如果当前物品不能放入背包 dp[i][w] = dp[i - 1][w] # 回溯找到具体选择了哪些物品 selected_items = [] w = capacity for i in range(n, 0, -1): if dp[i][w] != dp[i - 1][w]: selected_items.append(i) w -= weights[i - 1] # 计算总重量和总价值 total_weight = sum(weights[i - 1] for i in selected_items) total_value = sum(values[i - 1] for i in selected_items) return selected_items[::-1], total_weight, total_value # 输入数据 n = 7 weights = [35, 30, 60, 50, 40, 10, 25] values = [10, 40, 30, 50, 35, 40, 30] capacity = 150 # 调用函数 selected_items, total_weight, total_value = knapsack(n, weights, values, capacity) # 输出结果 print("选择物品:", " ".join(map(str, selected_items))) print("总重量:", total_weight) print("总价值:", total_value) ``` #### 需要注意的逻辑点 1. **初始化 `dp` 数组**：确保 `dp` 数组的初始值为 0，表示没有物品时的最大价值为 0。 2. **回溯选择的物品**：通过从 `dp` 数组中逆向查找，确定哪些物品被选中。 3. **边界条件**：当当前物品的重量大于背包剩余容量时，直接继承前一个状态的值。 希望这段代码能帮到你！如果有任何问题或需要进一步解释，随时告诉我。 ######[AI写代码神器 | 622点数解答 | 2024-11-27 08:35:50]