经典背包问题：动态规划求解最大价值及全方案输出

这个问题是一个典型的背包问题，可以使用动态规划来解决。我们可以定义一个二维数组`dp[i][j]`，其中`dp[i][j]`表示在考虑前`i`个物品，且背包容量为`j`的情况下，可以获得的最大价值。 对于每个物品，我们有两个选择：放入背包或不放入背包。如果放入背包，则背包的剩余容量需要减去该物品的重量，并且总价值加上该物品的价值。如果不放入背包，则背包的容量和价值都不变。 以下是基于这个思路的Python代码实现： ```python def knapsack(n, g, w, v): dp = [[0] * (g + 1) for _ in range(n + 1)] max_value = 0 max_value_index = 0 # 动态规划计算最大价值 for i in range(1, n + 1): for j in range(1, g + 1): if w[i - 1] <= j: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]) else: dp[i][j] = dp[i - 1][j] # 记录最大价值和对应的背包容量 if dp[i][j] > max_value: max_value = dp[i][j] max_value_index = j # 回溯找到最大价值对应的物品选择方案 def backtrack(index, capacity, path, results): if index == 0: if capacity == max_value_index: results.append(path) return # 不选择当前物品 backtrack(index - 1, capacity, path, results) # 选择当前物品 if w[index - 1] <= capacity: new_capacity = capacity - w[index - 1] new_value = dp[index - 1][new_capacity] + v[index - 1] if new_value == dp[index][capacity]: backtrack(index - 1, new_capacity, path + [index], results) results = [] backtrack(n, g, [], results) return max_value, results # 读取输入 n, g = map(int, input().split()) w = list(map(int, input().split())) v = list(map(int, input().split())) # 计算最大价值和选择方案 max_value, schemes = knapsack(n, g, w, v) # 输出最大价值 print(f"最大价值是{max_value}") # 输出选择方案 print(f"最大价值共有{len(schemes)}种选择方案,分别是:") for i, scheme in enumerate(schemes, 1): print(f"选择第{' '.join(map(str, scheme))}个物品") ``` 这段代码首先通过动态规划计算出最大价值，并记录了对应的背包容量。然后，通过回溯的方式找到所有满足最大价值的物品选择方案，并按照字典序排序输出。 注意，由于题目要求输出选择方案的顺序按字典序排序，我们需要在回溯的过程中维护选择方案的顺序。由于可能存在多种选择方案具有相同的最大价值，我们需要记录并输出所有这样的方案。 ######[AI写代码神器 | 775点数解答 | 2024-06-09 15:54:45]