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

这是一个经典的背包问题，可以使用动态规划来解决。 首先定义一个二维数组dp，其中dp[i][j]表示当背包容量为j时，前i个物品能够获得的最大价值。 然后，对于每个物品i，有两种情况： 1. 如果物品i的重量wi大于背包容量j，则物品i无法放入背包，此时dp[i][j] = dp[i-1][j]，即前i个物品的最大价值与前i-1个物品的最大价值相同。 2. 如果物品i的重量wi小于等于背包容量j，则物品i可以选择放入背包或者不放入背包。如果物品i放入背包，那么背包的容量减少wi，背包内物品的总价值增加vi，所以此时的最大价值可以通过比较两种情况得到：放入物品i时的最大价值dp[i-1][j-wi] + vi 和不放入物品i时的最大价值dp[i-1][j]，取较大的一个作为dp[i][j]。 最终，dp[n][g]就是我们所求的背包内物品的最大价值。 接下来，我们可以用递归的方式来得到最大价值所对应的物品选择方案。从dp[n][g]开始，向前递归，如果dp[i][j]等于dp[i-1][j]，说明第i个物品没有放入背包，我们继续递归到dp[i-1][j]；如果dp[i][j]等于dp[i-1][j-wi] + vi，说明第i个物品放入了背包，我们继续递归到dp[i-1][j-wi]。 具体实现如下： ```python def knapsack(n, g, weights, values): # 动态规划 dp = [[0] * (g+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, g+1): if weights[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]) # 得到最大价值的物品选择方案 def get_selections(i, j): if i == 0 or j == 0: return [[]] if weights[i-1] > j: return get_selections(i-1, j) else: selections = get_selections(i-1, j) for s in get_selections(i-1, j-weights[i-1]): s.append(i) selections.append(s) return selections selections = get_selections(n, g) # 输出结果 max_value = dp[n][g] num_selections = len(selections) print("最大价值是{}".format(max_value)) print("最大价值共有{}种选择方案，分别是：".format(num_selections)) for s in selections: s.sort() print("选择第{}个物品".format(" ".join(str(x) for x in s))) # 输入 n, g = map(int, input().split()) weights = list(map(int, input().split())) values = list(map(int, input().split())) # 使用函数求解 knapsack(n, g, weights, values) ``` 复杂度分析： - 时间复杂度：O(n*g)。需要计算dp二维数组，所以需要遍历n次物品，每次物品都需要遍历g次背包容量。 - 空间复杂度：O(n*g)。需要创建一个n+1行，g+1列的二维数组来存储dp。 ######[AI写代码神器 | 1605点数解答 | 2024-06-04 11:15:15]