背包问题
的背包问题(也被称为“背包问题”)是计算机科学中广为人知的组合优化问题。在本维基中,您将学习如何使用动态编程解决背包问题。
简介
背包问题可以表述如下:
给定一组不同的物品,每一件都有相应的价值和重量,确定你应该选择哪些物品,以使这些物品的价值最大化,而不超过你的背包的容量。
具体地说,假设我们有以下一组有价值的物品和给定的背包。
假设你有5件物品:
第一项 第二项 第三项 第四项 第五项 值: 5美元 10美元 3美元 2美元 3美元 重量: 4公斤 8公斤 3公斤 5公斤 2公斤 如果你的背包的重量限制是 最优解是什么?也就是说,你应该带哪些东西?
在这种情况下,解决方案是明确的。可以取第二项和最后一项,得到值 同时正好满足重量限制。在不违背问题约束的情况下,我们得到了最大的可能值。
然而,评估所有的可能性通常是非常不切实际的,所以我们想知道是否有更好的方法来处理这个问题。事实上,确实有,我们将在下一节中看到一个算法。
的伪代码
这个问题可以用简单的递归和二维数组来解决。
首先,我们应该为我们的问题找到一个方便的表示,并仔细地定义它。我们可以说我们有一组 物品,每个物品都有价值 和重量 我们的包的总重量限制是 .
现在我们构建一个 表:
表中的每个单元格都有值 ,在那里 代表了 行和 代表了 列。
用第一个集合的任意组合我们能得到的最大值是多少 不超过一定重量的清单项目 .有了这个,我们已经可以为我们的表识别一个递归:
背包问题的递归:
让我们试着解释一下这个递归:
假设你有一个特定的值 在您的表中,这意味着使用第一个的任何组合可以得到的最大值 您列出的项目的重量和每一项的重量之和不超过 .如果我们能做到这一点,显然我们也可以用第一个方法做到同样的事情 我们清单上的项目。我们找到了递归的第一种情况,非常简单
递归的第二种情况是怎样的呢?
鉴于 我们可以这么说 因为如果我们能得到某个值 使用第一个 项目的列表,我们也可以添加 物品的清单,以背包和它不会超过当前的限制 ,因为在我们得到 项,当前权重为 ,所以如果我们加上 项的当前权重将变为 ,因此我们保持当前权重等于权重限制,新的值将为 加上物品的值 ,然后 就变成了 .然而,这并不总是最好的选择。的值 是否更大,我们将用这个值代替 .还记得 只计算最大值,所以我们总是选择最好的选项。
最后,max ()
函数计算最佳选项(即找到最大的值)。
为了找到最大的可能值,我们只需要 即可能的最大值 当总重量小于容量时,我们的列表项 我们的袋子
背包问题的复杂性
在这个问题中,我们使用了一个高度矩阵 和宽度 ,我们的算法遍历每个单元格一次,就得到 操作。因此背包问题的复杂性是
12 3 4 5 6 7 8 9 10 11 12 13 14 |
|
现在我们来解决第一个例子:
给你一套五件物品 每个都在括号内有对应的值和权值
知道背包的重量限制后,你能得到的最大可能值是多少
让我们开始填充我们的表格:
我们知道第一行的所有单元格都是零,因此有了下表:
通过递归,我们知道了 .但是,当 我们有 .这是因为在这一点上 物品的重量是 而且 ,因此它满足递归的第二种情况的条件。我们知道
这
因此,这里的最大值是 ,然后 .做同样的事情 来 我们也会得到 所以我们的表格变成如下:
现在, 我们将继续做同样的过程。通过计算,我们会发现 从 来 而且 从 来 当 我们有 所以我们必须分析这两种情况:
而且
第二个选择是最好的,所以
做同样的操作,直到我们完成行,我们得到
只要继续使用递归来填满第三行和第四行,直到最后一行:
当你到达 你会看到
而且
对于最后一个单元格
而且
因此 .
这是我们完整的表格:
我们能得到的最大值是 ,这可以通过第二项和最后一项实现。通过这样做,总重量将是 (它等于容量,是10),总价值将是
下面是一个示例代码,你可以用它来解决这个问题:
12 34 56 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 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[我];}//使第一行中的每一个单元格都等于零为(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)低于给定的阈值。
- 不公正划分选区的形成每个城镇都有人口 ,和一个分数 给政党投票的人 .控制选区选择的政治集团(政党A)希望用数量来划分选区 尽可能的扩大,同时保持总人数在一定的限制下,并保持城镇的连续性。
约束优化是管理各种操作中最常见的难题之一。考虑到它的设置简单,可用来解决它的各种技术,以及它对实际问题的直接应用,背包问题是一个极好的玩具模型,可以为更高级的最优性问题提供丰富的训练场地。