经典 01 背包问题：给定物品与容量，求背包最大价值及选择方案

这是一个经典的01背包问题，可以使用动态规划算法解决。 首先，定义一个二维数组dp，其中dp[i][j]表示从前i个物品中选择一部分放入容量为j的背包中得到的最大总价值。 初始化dp数组，将其所有元素都设置为0。 然后，逐个遍历物品，对于第i个物品，有两种选择： 1. 如果将第i个物品放入背包中，则背包的总重量变为j-w[i]（j减去第i个物品的重量），背包的总价值变为dp[i-1][j-w[i]]+v[i]（背包的总价值加上第i个物品的价值）。 2. 如果不将第i个物品放入背包中，则背包的总重量和总价值都不变，即dp[i][j]=dp[i-1][j]。 取以上两种选择中的最大值作为第i个物品放入背包后的总价值，并更新dp[i][j]。 dp[n][g]即为问题的解，即最大总价值。 为了计算最大价值共有多少种选择方案，还需要使用一个数组cnt，其中cnt[i][j]表示前i个物品中选择物品总重量为j的方案数。 对于第i个物品，有两种选择： 1. 如果将第i个物品放入背包中，则物品总重量变为j-w[i]。 选择方案数为cnt[i-1][j-w[i]]，即前i-1个物品中选择物品总重量为j-w[i]的方案数。 2. 如果不将第i个物品放入背包中，则物品总重量不变。 选择方案数为cnt[i-1][j]，即前i-1个物品中选择物品总重量为j的方案数。 取以上两种选择的方案数之和作为第i个物品放入背包后的方案数，并更新cnt[i][j]。 cnt[n][g]即为最大价值的选择方案总数。 根据以上算法，可以编写如下的Python代码： ```python # 输入物品数量和背包容量 n, g = map(int, input().split()) # 输入物品重量和价值 w = list(map(int, input().split())) v = list(map(int, input().split())) # 初始化dp数组和cnt数组 dp = [[0] * (g + 1) for _ in range(n + 1)] cnt = [[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]) if dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]: cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - w[i - 1]] else: cnt[i][j] = cnt[i - 1][j] else: dp[i][j] = dp[i - 1][j] cnt[i][j] = cnt[i - 1][j] # 输出最大总价值 max_value = dp[n][g] print("最大价值是", max_value) # 输出选择方案总数 total_count = cnt[n][g] print("最大价值共有", total_count, "种选择方案,分别是:") # 输出选择方案 def dfs(i, j, path): if i <= 0 or j <= 0: print(path) return if j >= w[i - 1] and dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]: dfs(i - 1, j - w[i - 1], path + " 选择第" + str(i) + "个物品") if dp[i][j] == dp[i - 1][j]: dfs(i - 1, j, path) dfs(n, g, "") ``` 希望对你有帮助！ ######[AI写代码神器 | 1659点数解答 | 2024-06-08 23:25:09]