背包问题是一种组合优化问题,通常用于解决如何在一个给定容量的背包中放入物品,使得背包中物品的总价值最大。背包问题有很多变种,其中最常见的是0/1背包问题和完全背包问题。
在0/1背包问题中,每个物品只能选择一次。给定一组物品,每个物品有一个重量和一个价值,以及一个背包的最大承重。目标是选择一些物品放入背包,使得背包中物品的总价值最大,同时不超过背包的最大承重。
可以使用动态规划来解决0/1背包问题。定义一个二维数组dp
,其中dp[i][w]
表示在前i
个物品中选择,总重量不超过w
的情况下,可以获得的最大价值。
状态转移方程为:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] <= w
dp[i][w] = dp[i-1][w] if weight[i] > w
初始条件为:
dp[0][w] = 0 for all w
dp[i][0] = 0 for all i
最终答案为dp[n][W]
,其中n
是物品的数量,W
是背包的最大承重。
在完全背包问题中,每个物品可以选择无限次。目标同样是选择一些物品放入背包,使得背包中物品的总价值最大,同时不超过背包的最大承重。
定义一个二维数组dp
,其中dp[i][w]
表示在前i
个物品中选择,总重量不超过w
的情况下,可以获得的最大价值。
状态转移方程为:
dp[i][w] = max(dp[i-1][w], dp[i][w-weight[i]] + value[i]) if weight[i] <= w
dp[i][w] = dp[i-1][w] if weight[i] > w
初始条件为:
dp[0][w] = 0 for all w
dp[i][0] = 0 for all i
最终答案为dp[n][W]
,其中n
是物品的数量,W
是背包的最大承重。
以下是一个0/1背包问题的示例代码:
def knapsack_01(weights, values, max_weight):
n = len(weights)
dp = [[0] * (max_weight + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, max_weight + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][max_weight]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_weight = 5
print(knapsack_01(weights, values, max_weight)) # 输出:7
领取专属 10元无门槛券
手把手带您无忧上云