标签: knapsack-problem

这是我的任务

背包问题是计算机科学的经典之作.在其最简单的形式中,它涉及尝试将不同重量的物品装入背包中,以使背包最终具有指定的总重量.您不需要适合所有项目.例如,假设您希望您的背包重量恰好为20磅,并且您有五件物品,重量为11,8,7,6和5磅.对于少量物品,人类通过检查很好地解决了这个问题.所以你可能会发现,只有8,7和5种项目的组合总计达20个.

我真的不知道从哪里开始编写这个算法.应用于阶乘和三角数时,我理解递归.但是我现在迷路了.

当有1个房产时,我确实理解那里发生了什么.当有超过1个属性时,我遇到了解背包问题的问题.

我必须编写一个使用带有2个属性的背包算法的程序.老师告诉我们,它必须在一个3d数组中完成.我无法想象这样的阵列会是什么样子.

让我们说这是我的意见:

4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost

输出看起来像这样:

4    // the cheapest sum of costs of 2 records
1 3  // numbers of these 2 records

输出的解释:2组记录适合第1行输入:

(1) - 记录编号1和记录编号3

  1 1 …

假设有n个项目,例如i ₁,i ₂,...... i _n,它们中的每一个都具有已知的有界权重w ₁,w ₂,... w _n.还有一组m背包,例如k ₁,k ₂和k _m.背包是同质的,它们都具有相同的容量W.功能F可以确定每个背包的得分.F的输入是每个背包中的项目.所以,

Score of each knapsack i = F(Items in knapsack i)

现在我想把一些物品放在背包里,这样:

1. 背包中物品的重量不超过其容量W.
2. 所有背包的得分总和最大

是否存在针对此问题的多项式时间解决方案？

注意:问题是0-1,即每个项目都可以选择.所有问题参数都是有界的.

编辑1:是不是可以减少这个问题来装箱,然后得出结论,这是一个NP难问题？

编辑2在此问题中,每个项目都有三个属性,例如属性a _i,b _i和c _i.F函数是一个线性函数,它获取其中项目的属性并生成输出.

编辑3:本文似乎为多背包问题提出了一个精确的解决方案.可以用在我的情况下吗？

我正在尝试编写一个为分区Panel生成绘图的应用程序.

我有N个小隔间(2D矩形)(N <= 40).对于每个隔间,存在最小高度(minHeight [i])和最小宽度(minWidth [i]).面板本身也有一个MAXIMUM_HEIGHT约束.

这些N小室必须以列方式网格排列,以便满足每个小隔间的上述限制.

此外,每列的宽度由该列中每个隔间的最大minWidth决定.

此外,每列的高度应相同.这决定了面板的高度

我们可以在任何列的左侧空白处添加备用隔间,或者我们可以将任何隔间的高度/宽度增加到指定的最小值以外.但是我们不能旋转任何小隔间.

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

目前我只是通过忽略优化中的小隔间宽度来实现它.我只选择具有最大minHeight的隔间并尝试将其放入我的面板中.但是,它并不保证最佳解决方案.

我能比这更好吗？

编辑1:面板的MAXIMUM_HEIGHT = 2100mm,最小宽度范围(350mm至800mm),最小高度范围(225mm至2100mm)

编辑2:问题目标:最小化面板宽度(不是面板区域).

我正在寻找一个伪代码解决方案,实际上是多个背包问题(优化声明在页面的中间).我认为这个问题是NP Complete,因此解决方案不需要是最优的,而是如果它是相当有效且易于实现的,那将是好的.

问题是这样的:

• 我有很多工作项目,每个项目都有不同的(但是固定的和已知的)时间来完成.
• 我需要将这些工作项分成几组,以便拥有最少数量的组(理想情况下),每组工作项不超过给定的总阈值 - 比如1小时.

我对阈值很灵活 - 它不需要严格应用,但应该接近.我的想法是将工作项分配到箱中,其中每个箱代表阈值的90%,80%,70%等等.然后,我可以将占90%的项目与占10%的项目相匹配,依此类推.

有更好的想法吗？

只是一个好奇的问题.还记得在课堂小组中,教授会把人分成一定数量的小组(n)吗？

我的一些教授会列出n一个想要与之合作的n人和一个不想与每个学生一起工作的人的名单,然后神奇地将n学生与他们喜欢的人匹配的小组变成一组,避免与他们一起工作他们不喜欢的人.

对我来说,这个算法听起来很像背包问题,但我想我会问你对这类问题的解决方法是什么.

编辑:找到一篇描述与我的问题完全相同的ACM文章.为了似曾相识,请阅读第二段.

一个典型的Lisp方言可以使用自下而上的"动态编程"方法解决问题吗？

(请注意:我不是在谈论"memoization",据我所知,使用任何Lisp方言都是微不足道的.我真的在谈论自下而上的动态编程,你可以在这里构建你的数组自下而上然后使用您刚刚介绍的元素来计算下一个元素.)

例如,使用动态编程,"0-1背包"问题可以在任何其他方法失败的输入的伪多项式时间内求解.

一个必要的(不完整的)解决方案是:

for (int k = 1; k <= a.length; k++) {
    for (int y = 1; y <= b; y++) { 
        if (y < a[k-1]) {
            knap[k][y-1] = knap[k-1][y-1];
        } else {
            if (y > a[k-1]) {
                knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
            } else {
                knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
    }
}

各种Lisp方言有可能做到这一点吗？如果不是,为什么不呢？

尽管Knapsack问题陈述似乎与线性规划中的问题类似,但为什么线性规划算法类别中不包括背包问题？

我希望我的所有标签都具有相同的大小,而不是拥有一堆不同大小的链接.但是,我的目标是最大限度地减少制作云所需的空间,同时尽量减少使用的线路数量.

举个例子:

看起来像任何普通的标签云.然而,看看'roughdiamond'标签周围的所有额外空间,可以通过其他标签填充,例如靠近底部的"石头",这可以有效地消除云中的整个额外线.

在开始新线之前,我该怎么做才能填写上面可能的空格？我不是在谈论重新组织它们以找到所需的绝对最小行数.如果我正在查看图片中的列表,'pendant','howlite'和'igrice'会在第1行填充它,'roughdiamond'会转到第2行,因为第1行已满,'碧玺'会转到第3行,因为它不能适合第1或第2行,与"emberald"相同,但是'pearl'会进入第2行,因为它有适合那里的空间.我认为在CSS中可能会有一些方法可以简单地使链接折叠到它可以容纳的任何可填充空间中.

考虑以下输入的典型背包问题.

V = [10,8,12]
W = [2,3,7]
i =  1,2,3
C = 10

我尝试使用memoization进行递归来解决此示例但发现没有重叠的子问题.

递归程序的签名:

knapsack(int c, int i) 

最初称为 knapsack(10,1)

解决方案的方法类似于https://www.youtube.com/watch?v=6h6Fi6AQiRM和https://www.youtube.com/watch?v=ocZMDMZwhCY中所述.

动态编程如何帮助减少这些Knapsack样本的时间复杂度？如果它没有帮助改善这种情况的时间复杂度,那么DP解决方案的最坏情况复杂性也与基于后向跟踪搜索相同,即2到功率n [ 忽略修剪,就像修剪应用那样复杂性将降低两者解决方案再次DP将不会比非memoized递归解决方案更好 ]

**在上面的示例中是否真的缺少子问题,或者我遗漏了什么？**