背包问题

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

背包的问题可以表述如下:

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

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

假设你有一组5个项目:

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

如果你背包的重量限制是 $10\text{kg}，$什么是最佳解决方案？也就是说，你应该随身携带哪些物品？

---

在这种情况下，解决方案是明确的。一个会取第二项和最后一项，得到值为 $\ 13美元$在完全满足权重限制的情况下，我们在不违反问题约束的情况下实现了最大可能值。 $_\方格$

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

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

首先，我们应该为我们的问题找到一个方便的表示，并仔细定义它 $N$物品，每个物品都有价值 $沃伊$和重量 $沃伊$，我们的包总重量限制为 $W$．

现在我们构造一个 $n次/W$表:

表1

表中的每个单元格都有值 $t (i, j)$,在那里 $我$代表了 $i^\text{th}$争吵 $J$代表了 $j^\text{th}$列。

$t (i, j)$我们能得到的最大值是使用第一个集合的任意组合吗 $我$不超过一定重量的列表项目 $J$。这样，我们就可以为表识别递归：

背包问题的递归:

$t[i，j]=\begin{cases}t[i-1，j]\hspace{5pt}&\text{if}\hspace{5pt}w\u i>j\\\ max\big（t[i-1，j]，t[i-1，j-w\u i]+v\u i\big）\hspace{5pt}&\text{if}\hspace{5pt}w\leq j.\end{cases}$

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

假设你有一个确定的值 $张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[i-1，j-w_i]$使用第一个 $张$项目的列表，我们也可以添加 $i^\text{th}$物品清单上的背包，它将不会超过目前的限制 $J$因为在我们得到 $i^\text{th}$项，当前权重为 $j-w_i$，因此，如果我们添加 $i^\text{th}$项的当前权重将变为 $j-w_i + w_i = j$，因此我们保持当前权重等于权重限制，新值将为 $t[i-1，j-w_i]$加上该项的值 $沃伊$然后 $t (i, j)$就变成了 $t[i-1，j-w_i]+v_i$．然而，这并不总是最好的选择。如果 $张t [j]$Is bigger，我们将使用这个值来代替 $t[i-1，j-w_i]$回想起 $t (i, j)$只计算最大值，因此我们将始终选择最佳选项。

最后是max ()函数评估最佳选项（即找到最大值）。

为了找到最大可能的价值，我们只需要 $t[n，W]$ $($i、 e.使用 $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]

现在我们将解决第一个示例：

您将获得一组五个项目 $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

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

$t[i-1，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\big[i-1，j-w[i]\big]+v_i=t[4,7]+v_i=8+3=11。$

最后一个单元格

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

和

$t\big[i-1，j-w[i]\big]+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$

以下是可以用来解决此问题的示例代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17日18 19 20 21日22日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

#包括< iostream >#包括因为<字符串>/*背包问题*///W=背包容量/ / w[我]= i物品的重量/ / v[我]= i项的值//比较两个值并返回较大的那个int最大限度(intA.,intB）{如果(A.＞＝B)返回A.;其他的返回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[我]；}//使第一行中的每个单元格都等于零对于(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[我]);}库特<<"\ n";//显示表格对于(我=0;我＜＝N;我++）{库特<<"\ n";对于(J=0;J＜＝W;J++）{库特<<表格[我］［J]<<”“;}}//打印答案库特<<"\ n最大值：\ n";库特<<表格[N］［W]；库特<<"\n\n";返回0;}

虽然简单地陈述和解决了背包问题，但如果不将背包问题用作许多实际问题的原型，背包问题可以直接映射。直接应用包括：

• 一家运输公司试图在不破坏运输飞机重量的前提下，把同样多的包裹装进运输飞机，
• 专业运动队希望组建一支满足各种统计预测且不打破工资上限的队伍，以及
• Soylent需要满足每日的营养需求，同时保持每次食用一定量的粉末。

更有趣的应用包括：

• 对冲基金需要投资以使潜在收益最大化，同时将风险价值(VaR)保持在给定的阈值以下。
• 划分选区的政治区域的形成。每个城镇都有人口 $p_i$，和一个分数 $福伊$投票给该党的人口中 $A.$．控制选区选择的政治团体(政党甲)要以数量作选区 $\dfrac{\sum\u i p\u i f\u i}{\sum\u ip\u i}$尽可能多，同时保持总人数低于一定的限制，并保持一组连续的城镇。

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