在 Python 中使用动态规划解决 0/1 背包问题

作者

在本文中，我们将使用动态规划解决 0/1 背包问题。

动态规划是一种通过将优化问题分解为更简单的子问题并利用整个问题的最优解取决于其子问题的最优解这一事实来解决优化问题的算法技术。

0/1 背包可能是动态规划中最常见的问题。为了掌握动态规划的窍门，这也是一个需要学习的大问题。

在本教程中，我们将了解 0/1 Knapsack 到底是什么以及如何在 Python 中使用动态编程来解决它。

让我们开始吧。

0/1 背包的问题陈述

动态规划的问题描述如下：

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

首先，我们有一个权重数组，其中包含所有项目的权重。我们还有一个值数组，其中包含所有物品的值，并且我们还有背包的总重量。

有了这些信息，我们需要找到在重量限制范围内可以获得的最大值。

该问题称为 0/1 背包，因为我们可以将一个项目作为一个整体包含在内，也可以将其排除。也就是说，我们不能拿走一件物品的零头。

我们举个例子来理解一下。

取以下输入值。

val = [50,100,150,200]
wt = [8,16,32,40]
W = 64

在这里，当我们包含第 1,2 和 4项时，我们获得最大利润，总计为200 + 50 + 100 = 350。

因此总利润为：

350

如何使用动态规划求解0/1背包？

为了使用动态规划求解 0/1 背包，我们构建了一个具有以下维度的表。

[n + 1][W + 1]

表的行对应于从0 到 n的项目。

表中的各列对应于从0 到 W 的重量限制。

表的最后一个单元格的索引为：

[n][W]

索引为[i][j]的单元格的值表示考虑从0到i的物品且总重量限制为j时可能的最大利润。

填写表格后，我们的答案将位于表格的最后一个单元格中。

表格怎么填？

我们首先将第 0 行和第 0 列设置为 0。我们这样做是因为第 0 行意味着我们没有对象，第 0 列意味着可能的最大权重为 0。

现在对于每个单元格 [i][j]，我们有两个选项：

  1. 要么我们将对象 [i] 包含在我们的最终选择中。
  2. 或者我们不将对象 [i] 包含在我们的最终选择中。

我们如何决定是否将对象 [i] 包含在我们的选择中？

包含 object [i] 需要满足两个条件：

  1. 包含物体[i]后的总重量不应超过重量限制。
  2. 与不包含对象时相比，包含对象 [i] 后的利润应该更大。

我们把对0/1背包的理解转化为python代码。

解决0/1背包问题的Python代码

让我们使用以下列表理解方法创建一个表：

table = [[0 for x in range(W + 1)] for x in range(n + 1)]

我们将使用嵌套的for 循环来遍历表格并在每个单元格中填充整体。

我们将以自下而上的方式填充表格。

for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                table[i][j] = 0
            elif wt[i-1] <= j:
                table[i][j] = max(val[i-1] 
+ table[i-1][j-wt[i-1]],  table[i-1][j])
            else:
                table[i][j] = table[i-1][j]
  

让我们逐行分解代码。

if i == 0 or j == 0:
   table[i][j] = 0

这部分代码负责将第0行第0列设置为0。

elif wt[i-1] <= j:

这行代码检查第 i(th) 个物体的重量是否小于该单元 (j) 允许的总重量。

table[i][j] = max(val[i-1] 
+ table[i-1][j-wt[i-1]],  table[i-1][j])

这行代码负责从我们可用的两个选项中选择最大值。我们可以包含该对象或排除它。

这里术语table[i – 1][j]表示不包括第 i 项。val [i – 1] + table[i – 1][j – wt[i – 1]] 项表示包含第 i 项。

else:
  table[i][j] = table[i-1][j]

当第 i 个对象的重量大于允许的限制 (j) 时，将访问这部分循环。

填写完表格后，我们可以返回表格的最后一个单元格作为答案。

return table[n][W]

背包求解函数的完整代码

解决背包问题的函数的完整代码如下：

def knapSack(W, wt, val):
    n=len(val)
    table = [[0 for x in range(W + 1)] for x in range(n + 1)]
 
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                table[i][j] = 0
            elif wt[i-1] <= j:
                table[i][j] = max(val[i-1] 
+ table[i-1][j-wt[i-1]],  table[i-1][j])
            else:
                table[i][j] = table[i-1][j]
   
    return table[n][W]

让我们尝试运行上面示例的函数。

val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
 
print(knapSack(W, wt, val))

完整代码

这是供您在系统上运行的完整代码。

def knapSack(W, wt, val):
    n=len(val)
    table = [[0 for x in range(W + 1)] for x in range(n + 1)]
 
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                table[i][j] = 0
            elif wt[i-1] <= j:
                table[i][j] = max(val[i-1] 
+ table[i-1][j-wt[i-1]],  table[i-1][j])
            else:
                table[i][j] = table[i-1][j]
   
    return table[n][W]
 
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
 
print(knapSack(W, wt, val))

运行代码后，我们得到以下输出：

350

结论

本教程是关于在 Python 中使用动态编程解决 0/1 Knapsack 问题。我们希望您和我们一起学习愉快！