背包问题

的背包问题(也被称为“背包问题”)是计算机科学中广为人知的组合优化问题。在本维基中，您将学习如何使用动态规划解决背包问题。

背包问题可以这样表述:

给定一组不同的物品，每个物品都有相应的价值和重量，决定你应该选择哪些物品，以便在不超过背包容量的情况下最大化这些物品的价值。

具体地说，想象我们有以下一组有价值的物品和给定的背包。

假设你有一组5个项目:

	第一项 $\水平间距{5毫米}$	第二项 $\水平间距{5毫米}$	第三项 $\水平间距{5毫米}$	第四项 $\水平间距{5毫米}$	第五项 $\水平间距{5毫米}$
值: $\水平间距{10毫米}$	5美元	10美元	3美元	2美元	3美元
重量:	4公斤	8公斤	3公斤	5公斤	2公斤

如果你的背包的重量限制是 $10 \文本{公斤},$最优解是什么?也就是说，你应该带哪些东西?

---

在这种情况下，解决方案很明显。一个将获取第二个和最后一个项，获得值 $\ 13美元$同时完全达到体重限制。我们在不违反问题约束的情况下获得了最大可能值。 $_ \广场$

然而，总的来说，评估所有的可能性是非常不实际的，所以我们想知道是否有更好的方法来处理这个问题。事实上，有，我们将在下一节看到一个算法。

这个问题可以用简单的递归和二维数组来解决。

首先，我们应该为我们的问题找到一个方便的表示，并仔细地定义它。我们可以说我们有一组 $n$物品，每个物品都有价值 $v_i$和重量 $w_i$我们的包的总重量限制在 $W$．

现在我们构造一个 $n \ W倍$表:

表1

表中的每个单元格都有值 $t (i, j)$,在那里 $我$代表了 $我^ \文本{th}$行和 $j$代表了 $j ^ \文本{th}$列。

$t (i, j)$第一个集合的任意组合都能得到最大值吗 $我$三清单物品重量不超过一定重量者 $j$．通过这个，我们已经可以确定表的递归:

背包问题的递归:

$t (i, j) = \开始{病例}t [j]张,\水平间距{5 pt}和{如果}\ \文本水平间距{5 pt} w_i > j \ \ \马克斯\大(t[张j],[张,j-w_i] + v_i \大)\水平间距{5 pt}和{如果}\ \文本水平间距{5 pt} w_i \ leq j。\{病例}结束$

让我们试着解释这个递归:

假设你有一个确定的值 $张t [j]$在您的表中，这意味着您可以使用第一种方法的任意组合获得最大值 $张$您所列物品的重量总和不超过每件物品的重量 $j$．如果我们能做到这一点，显然我们也可以用第一个方法来做同样的事情 $我$我们清单上的项目。我们找到了递归的第一种情况，非常简单:

$t (i, j) = t [j]张,\水平间距{5 pt}{如果}\ \文本水平间距{5 pt} w_i > j。$

递归的第二种情况是怎样的呢?

鉴于 $w_i \ leq j$，我们可以这么说 $t (i, j) = t(张,j-w_i) + v_i$因为如果我们能得到一个确定的值 $t(张,j-w_i)$使用第一个 $张$项的列表中，还可以添加 $我^ \文本{th}$将清单上的物品放入背包内，它不会超过当前的限额 $j$，因为在我们得到 $我^ \文本{th}$项，当前权重为 $j-w_i$，如果我们加上 $我^ \文本{th}$项目当前的重量将成为 $j-w_i + w_i = j$，因此我们保持当前的重量等于重量限制，而新值将为 $t(张,j-w_i)$加上物品的价值 $v_i$,然后 $t (i, j)$就变成了 $t(张,j-w_i) + v_i$．然而，这并不总是最好的选择。的值 $张t [j]$更大时，我们将使用这个值而不是 $t(张,j-w_i)$．还记得 $t (i, j)$只计算最大值，所以我们总是会选择最好的选项。

最后,max ()函数评估最佳选择(即找到最大的值)。

为了找到最大的可能值，我们只需要 $t (n, W)$ $（$即，使用 $n$当总重量小于容量时，我们的列表项 $W$我们的袋子 $）.$

背包问题的复杂性

在这个问题中，我们使用了一个高度矩阵 $n$和宽度 $W$，我们的算法遍历每个单元格一次，这使得 $n \ W倍$操作。因此，背包问题的复杂性是 $O (n \ * W)。$

12 3 4 5 6 7 8 9 10 11 12 13 14

# n:项目数量# v[i]:第i个元素的值，w[i]:第i个元素的权重# W =背包容量背包（n，v，w，W）为j＝0来j＝Wt［0，j］＝0为我＝1来n为j＝0来W如果w［我］>jt［我，j］＝t［我-1，j］其他的t［我，j］＝马克斯（t［我-1，j]，t［我-1，j-w［我]]+v［我])返回t［n] [W］

现在我们来解第一个例子:

你会得到一组5个项目 $I_1、I_2 I_3、I_4 I_5$每一个都有相应的值和括号内的权重 $[v_i, w_i]:$

$I_1 = (5 4) \ \ I_2 =(10、8)\ \ I_3 = 3, 3, \ \ I_4 =(2、5)\ \ I_5 =[3 2]。$

知道背包的重量限制后，你能得到的最大值是多少 $10 ?$

---

让我们开始填充表格:

我们知道第一行中的所有单元格都是零，因此有了下面的表格:

表二

用递归，我们知道 $t (1,0) = t [1] = [1, 2] = t [1,3] = 0$．但是,当 $j = 4,$我们有 $t [1] = [1,4] = 5$．这是因为在这一点上 $w \[我]leq j,$物品的重量为 $w [1] = 4$而且 $j = 4$，所以它满足递归第二种情况的条件。我们知道

$张t [j] = t [0, 4] = 0$

这

$t \[大张,j-w[我]大\]+ v_i = t (0,0) + v_i = 0 + 5 = 5。$

因此，这里的最大值为 $5$,然后 $t (i, j) = t [1,4] = 5$．同样的方法 $j = 5$来 $j = 10,$我们也会得到 $5，$因此我们的表格如下:

table3

现在, $我= 2。$我们会继续做同样的过程。通过计算，我们会看到 $t [2] = 0$从 $j = 0$来 $j = 3$而且 $t [2] = 5$从 $j = 4$来 $j = 7。$当 $j = 8,$我们有 $w \[我]leq j,$所以我们要分析两种情况:

$张t [j] = t (1,8) = 5$

而且

$t \[大张,j-w[我]大\]+ v_i = t (1,0) + v_i = 0 + 10 = 10。$

第二种选择是最好的，所以

$t (i, j) = t[2, 8] = 10。$

做同样的事情，直到我们完成这一行，我们得到

table4

只要继续使用递归来填充第三和第四行，直到你得到最后一行:

table5

当你到达 $t(5、9),$你会看到

$张t [j] = t(4、9)= 10$

而且

$t \[大张,j-w[我]大\]+ v_i = t(4、7)+ v_i = 8 + 3 = 11。$

对于最后一个单元格

$张t [j] = t[4、10]= 10$

而且

$t \[大张,j-w[我]大\]+ v_i = t[4、8]+ v_i = 10 + 3 = 13。$

因此 $t (i, j) = t [5 10] = 13$．

这是我们完整的表格:

我们能得到的最大值是 $t [n, W] = [5 10] = 13$，可以通过使用第二项和最后一项来实现。这样做，总重量将是 $10$(它等于容量，是10)总和将是 $13.$

下面是你可以用来解决这个问题的示例代码:

12 34 56 7 8 9 10 11 12 13 14 15 16 17 18 19 20 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

# include< iostream ># include因为<字符串>/ * * /背包问题/ / W =背包容量/ / w[我]= i物品的重量/ / v[我]= i项的值//比较两个值并返回较大的那个int最大（int一个，intb) {如果（一个> =b）返回一个；其他的返回b；｝使用名称空间性病；int主要（）｛intW，v［One hundred.]，w［One hundred.];int我，j，n；int表格［One hundred.] [10000];//读取W和条目数ncin>>W>>n；//读取每一项的重量和值为（我＝1；我< =n；我++）｛cin>>w［我］>>v［我];｝//将第一行中的每个单元格设为0为（j＝0；j< =W；j++）表格［0] [j］＝0；//填充表为（我＝1；我< =n；我++）为（j＝0；j< =W；j++) {//递归的第一种情况如果（w［我］>j）表格［我] [j］＝表格［我-1] [j];/ /第二个案例其他的表格［我] [j］＝最大（表格［我-1] [j]，表格［我-1] [j-w［我]]+v［我]);｝cout<<＂\ n＂；/ /显示表为（我＝0；我< =n；我++) {cout<<＂\ n＂；为（j＝0；j< =W；j++) {cout<<表格［我] [j］<<”“；｝｝/ /输出答案cout<<＂\ n最大值:\ n＂；cout<<表格［n] [W];cout<<＂\ n \ n＂；返回0；｝

虽然简单的陈述和简单的解决，背包问题可以直接映射，如果不用作许多实际问题的原型。直接申请包括:

• 一家航运公司试图在不破坏载重能力的情况下将尽可能多的包裹体积装入一架运输飞机，
• 一支职业运动队希望建立一支球队，既能满足各种统计预测，又不打破工资上限
• Soylent需要满足每天的营养需求，同时保持每一份给定的粉量。

更有趣的应用包括:

• 对冲基金需要进行投资，以使潜在收益最大化，同时保持风险价值(VaR)低于给定的阈值。
• 不公正划分政治选区的形成每个城镇都有人口 $p_i$，和一个分数 $f_i$投票给政党的人口 $一个$．控制选区的政治团体(政党甲)要用数量来做选区 $\ dfrac {\ sum_i p_i f_i} {\ sum_ip_i}$尽可能多，同时保持总人口数低于一定限度，并保持一系列连续的城镇。

约束优化是管理各种操作中最常见的难题之一。考虑到它的设置简单，解决它的各种技术，以及它对实际问题的直接应用，背包问题是一个优秀的玩具模型，并为更高级的最优化问题提供了丰富的训练场地。