用python写出 有n个重量分别为w={w_1,w_2,…,w_n}的物品，他们的价值分别为v={v_1,v_2,…,v_n}，给定一个容量为v的背包。 设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，并且背包内物品的总价值达到最大。 输入格式 第一行输入两个整数n、g，其中n表示物品的数量，g表示背包的容量体积。 第二行输入n个整数，整数间以空格分隔，表示n个物品的重量w_i 第三行输入n个整数，整数间以空格分隔，表示n个物品的价值v_i 输出格式 第一行输出最大价值是v，v是计算得到的背包内物品总价值的最大值 第二行输出最大价值共有k种选择方案,分别是:，k是最大价值时，背包内物品选择的方案总数。 随后k行输出选择第x1 x2 ... xn个物品，x1、x2、...xn、是选择的第几个物品，中间以空格分隔，输出顺序以字典序排序。 输入样例 5 13 3 4 4 5 10 4 9 9 10 24 输出样例 最大价值是28 最大价值共有2种选择方案,分别是: 选择第2 3 4个物品 选择第1 5个物品

```python def knapsack(n, g, w, v): dp = [[0] * (g + 1) for _ in range(n + 1)] 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] max_value = dp[-1][-1] solutions = [] def find_solutions(i, j, path): if i == 0 or j == 0: solutions.append(path) return if dp[i][j] == dp[i - 1][j]: find_solutions(i - 1, j, path) else: find_solutions(i - 1, j - w[i - 1], path + [i]) find_solutions(n, g, []) return max_value, solutions if __name__ == "__main__": n, g = map(int, input().split()) w = list(map(int, input().split())) v = list(map(int, input().split())) max_value, solutions = knapsack(n, g, w, v) print("最大价值是{}".format(max_value)) print("最大价值共有{}种选择方案，分别是：".format(len(solutions))) for solution in solutions: print("选择第", end="") print(" ".join(str(x) for x in solution), end="个物品\n") ``` [2024-06-09 17:41:36 | AI写代码神器 | 458点数解答]