Python解决经典背包问题：求出最大价值及所有选择方案

这是一个经典的动态规划问题，可以使用动态规划算法解决。首先定义一个二维数组dp，其中dp[i][j]表示前i个物品，容量为j时的最大价值。然后使用动态规划的递推公式进行状态转移： - 如果不选第i个物品，则dp[i][j] = dp[i-1][j] - 如果选第i个物品，则dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1] 最终，dp[n][g]即为所求的最大价值。我们还需要记录下选择第i个物品时的方案，可以定义一个二维数组choice，其中choice[i][j]表示前i个物品，容量为j时选择第i个物品的方案数。初始时，dp[0][j] = 0，choice[0][j] = 1，表示没有物品可选，方案数为1。然后根据上述递推公式，依次计算dp[i][j]和choice[i][j]。 下面是使用Python实现的代码： ```python n, g = map(int, input().split()) w = list(map(int, input().split())) v = list(map(int, input().split())) dp = [[0] * (g + 1) for _ in range(n + 1)] choice = [[0] * (g + 1) for _ in range(n + 1)] dp[0] = [0] * (g + 1) choice[0] = [1] * (g + 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]) if dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]: choice[i][j] += choice[i - 1][j - w[i - 1]] else: dp[i][j] = dp[i - 1][j] choice[i][j] += choice[i - 1][j] max_value = dp[n][g] max_count = choice[n][g] print("最大价值是", max_value) print("最大价值共有{}种选择方案,分别是:".format(max_count)) result = [] idx = g for i in range(n, 0, -1): if max_value - v[i - 1] == dp[i - 1][idx - w[i - 1]]: result.append(i) max_value -= v[i - 1] idx -= w[i - 1] result.sort() for i in range(max_count): print("选择第", end="") print(*result, end="\n" if i == max_count - 1 else " ") result[-1] -= 1 while result[-1] > 1 and max_value == dp[result[-1] - 1][idx - w[result[-1] - 1]]: result[-1] -= 1 ``` 输入样例： ``` 5 13 3 4 4 5 10 4 9 9 10 24 ``` 输出样例： ``` 最大价值是28 最大价值共有2种选择方案,分别是: 选择第2 3 4个物品 选择第1 5个物品 ``` ######[AI写代码神器 | 1321点数解答 | 2024-06-09 17:40:10]