以下是一个解决背包问题的初学者Python代码示例:
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][capacity]
这段代码使用动态规划的思想来解决背包问题。通过创建一个二维数组dp
来保存中间结果,其中dp[i][j]
表示前i
个物品在背包容量为j
时的最大价值。
代码中的两个嵌套循环用来遍历所有可能的物品和背包容量组合。如果当前物品的重量小于等于背包容量,则可以选择放入该物品或不放入该物品。选择放入该物品时,当前状态的价值等于不放入该物品时的价值加上该物品的价值。选择不放入该物品时,当前状态的价值等于前一个状态的价值。取两者的最大值作为当前状态的最大价值。
最后返回dp[n][capacity]
即为问题的解,其中n
为物品的个数。
这个代码示例适用于背包问题的0/1版本,即每个物品只能选择放入或不放入背包。如果需要解决其他版本的背包问题,可以根据具体需求进行相应的修改。
上一篇:背包变体/组合优化