嗨,大家好!在本教程中,我试图解释背包问题。在面试过程中你会在某个地方遇到这个问题。
我们将使用递归方法来解决这个问题。如果您不知道递归是如何工作的,请查看下面的教程。
阅读有关递归的更多信息: Python 中的递归
背包问题简介
有一个小偷,他的背包总重量可以容纳 capacity
. 他从这个地方有 n 件不同重量和价格的物品要偷。
我们的目标是创建一个名为 的函数, knapsack
该函数将找出这些物品的子集,考虑到所有物品的总重量不超过capacity
背包的给定重量,从而为小偷带来最大利润。
另请阅读:用 Python 解决朋友旅行问题 [Google 面试问题]
下图同样说明了这一点。
使用递归解决Python中的背包问题
我们将考虑对于每个物品,小偷有两个选择:要么包含该物品,要么排除该物品并且不拾取它。
如果小偷包含了一件物品,我们将搜索剩余n-1件物品的最大利润,并且还会根据所包含物品的重量来减少容量。
在这种情况下,总利润 将为:商品的价格 + 剩余 n-1 件商品的利润(容量 – 商品的重量)
如果一个人排除了该商品,我们将只找到商店中剩余n-1件商品的利润。在这种情况下,利润将为: 剩余产能的 n-1 项利润
最终的答案将是两种情况下的最大利润。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 号
|
def knapsack(n,capacity,weights,prices): if (n = = 0 or capacity = = 0 ): return 0 if (weights[n - 1 ]>capacity): return knapsack(n - 1 ,capacity,weights,prices) else : return max (prices[n - 1 ] + knapsack(n - 1 ,capacity - weights[n - 1 ],weights,prices), knapsack(n - 1 ,capacity,weights,prices)) weights = [ 1 , 2 , 3 , 4 ] prices = [ 50 , 200 , 150 , 100 ] n = 4 capacity = 7 print (knapsack(n,capacity,weights,prices)) |
执行当前代码后收到的输出是400,这是正确的输出。
感谢您花时间阅读本教程!我希望您现在已经清楚背包问题了。
快乐学习!😇