Python中的0/1背包问题

在此问题中，我们给出了两个长度为 N 的数组，其中 N 是我们可以使用的物品数量。其中一个数组包含单个物品的利润值，第二个数组包含物品的重量。我们还给出了一个值 W，指定背包的最大容量（按重量计算）。我们的任务是找到装满背包后可能获得的最大利润。该问题之所以命名为 0/1，是因为我们只能选择完整的物品，而不能选择它们的零碎部分。让我们通过一些例子来理解这个问题。

示例

输入： N = 6, W = 50, profit = [5, 1, 7, 9, 4, 6], weight = [10, 20, 30, 11, 25, 20]

输出 20

方法 - 1

在此方法中，我们将使用暴力破解技术。我们将生成所有可能的物品子集，并计算所有这些子集的利润。然后，在所有利润值中，我们将找到在给定约束条件下可能获得的最大利润。所有子集物品的总重量应小于 W。

要形成子集，我们有两种情况。要么将当前物品添加到集合中，要么不将当前物品添加到集合中。但是，有三个条件需要检查才能决定这两种情况。

我们将按以下方式进行：

• 首先，我们将检查当前物品的重量是否大于背包的当前容量。如果是，则我们不将当前物品包含在背包中。
• 如果重量小于背包的当前容量，那么我们需要根据利润来决定。如果将物品添加到子集后的利润比排除它时更高，那么我们将包含它；否则，我们将排除该物品。

这是上述方法在 Python 中的实现。

代码

输出

20

时间复杂度：在此方法中，我们检查所有可能的结果，从而到达递归树的所有可能分支。因此，此方法的复杂度是指数级的，即 O(2^N)。

辅助空间：我们使用额外的空间来存储递归堆栈；因此，此方法的空间复杂度为 O(N)。

方法 - 2

在此方法中，我们将使用动态规划来解决此问题。在上述递归方法中，有许多子问题。为了只解决一次子问题并降低时间复杂度，我们将使用动态规划方法。我们将把子问题的解决方案存储在一个二维数组中。子问题将由两个参数决定。参数是剩余物品的数量和背包当前的重量容量。二维数组将有助于以恒定时间获取子问题的解决方案，而不是以非线性时间解决它们。

以下是上述方法在 Python 中的实现。

代码

输出

20

时间复杂度：动态规划函数的时间复杂度是树的宽度和高度的乘积。因此，此方法的复杂度为 O(N * W)。

辅助空间：此方法的空间复杂度比前一种方法高，因为我们还存储了二维动态规划数组。因此，这次总的空间复杂度将是 O(N * W) + O(N)，其中第一部分是由于数组，第二部分是由于递归堆栈。

我们也可以使用循环来解决上述问题。让我们看看循环的代码。

代码

输出

20

此方法的时间和空间复杂度相同。