使用递归解决 Python 中的 0-1 背包问题

作者

嗨，大家好！在本教程中，我试图解释背包问题。在面试过程中你会在某个地方遇到这个问题。

我们将使用递归方法来解决这个问题。如果您不知道递归是如何工作的，请查看下面的教程。

阅读有关递归的更多信息：  Python 中的递归

背包问题简介

有一个小偷，他的背包总重量可以容纳 capacity. 他从这个地方有 n 件不同重量和价格的物品要偷。

01 背包问题

我们的目标是创建一个名为 的函数， knapsack 该函数将找出这些物品的子集，考虑到所有物品的总重量不超过capacity背包的给定重量，从而为小偷带来最大利润。

另请阅读：用 Python 解决朋友旅行问题 [Google 面试问题]

下图同样说明了这一点。

01 背包问题1

使用递归解决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，这是正确的输出。

感谢您花时间阅读本教程！我希望您现在已经清楚背包问题了。

快乐学习！😇