0 - 1背包问题：用动态规划求解最大价值及选择方案

这个问题是经典的0-1背包问题，它可以使用动态规划来解决。首先，我们需要定义两个数组，dp[i][j]表示前i个物品中，容量为j的背包所能达到的最大价值；path[i][j]表示达到dp[i][j]这个价值时，最后一个被放入背包的物品的编号。然后，我们可以通过遍历物品和背包容量来填充这两个数组。 下面是一个可能的实现： ```python def knapsack(n, g, w, v): dp = [[0 for _ in range(g + 1)] for _ in range(n + 1)] path = [[-1 for _ in range(g + 1)] for _ in range(n + 1)] max_value = 0 max_value_index = -1 for i in range(1, n + 1): for j in range(1, g + 1): if w[i - 1] <= j: if dp[i - 1][j] < dp[i - 1][j - w[i - 1]] + v[i - 1]: dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1] path[i][j] = i else: dp[i][j] = dp[i - 1][j] path[i][j] = path[i - 1][j] else: dp[i][j] = dp[i - 1][j] path[i][j] = path[i - 1][j] if dp[i][j] > max_value: max_value = dp[i][j] max_value_index = j def print_path(i, j): if i == 0 or j == 0: return if path[i][j] != -1: print_path(i - 1, j - w[path[i][j] - 1]) print(path[i][j], end=' ') print(f"最大价值是{max_value}") count = 0 for j in range(g, max_value_index - 1, -1): if dp[n][j] == max_value and path[n][j] != -1: count += 1 print(f"选择第", end='') print_path(n, j) print() print(f"最大价值共有{count}种选择方案,分别是:") # 读取输入 n, g = map(int, input().split()) w = list(map(int, input().split())) v = list(map(int, input().split())) # 调用函数 knapsack(n, g, w, v) ``` 此代码首先计算了最大价值和达到最大价值时背包的容量。然后，它定义了一个递归函数`print_path`来打印出达到最大价值时选择的物品编号。它遍历所有可能的背包容量，找出所有达到最大价值的方案并打印出来。 注意，此代码在物品编号的打印上是从1开始的，如果要求从0开始，需要做一些小的调整。 ######[AI写代码神器 | 767点数解答 | 2024-06-08 23:27:17]