Python实现背包问题：找出最大价值及所有最优选择方案

```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 j >= w[i - 1]: 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") ``` ######[AI写代码神器 | 456点数解答 | 2024-06-14 16:34:33]