问题标签 [knapsack-problem]

与其拥有一堆大小不同的链接，我希望我的所有标签都具有相同的大小。但是，我的目标是尽量减少制作云所需的空间量，也就是尽量减少使用的行数。

举个例子：

_{（来源：stevethomas.com.au）}

看起来像任何普通的标签云。然而，看看'roughdiamond'标签周围的所有额外空间，这些额外的空间可以被其他标签填充，比如靠近底部的'stone'，这可以有效地从云中消除一整条额外的线。

在开始新行之前，我将如何让单词填充它们上方的任何空间？我不是在谈论重新组织它们以找到所需的绝对最少行数。如果我浏览图像中的列表，“pendant”、“howlite”和“igrice”将进入第 1 行填满，“roughdiamond”将进入第 2 行，因为第 1 行已满，“电气石”将转到第 3 行，因为它不适合第 1 行或第 2 行，与 'emberald' 相同，但 'pearl' 会转到第 2 行，因为它可以放在那里，因为有额外的空间。我认为在 CSS 中可能会有某种方式来执行此操作，这只会导致链接折叠到它可以容纳的任何可填充空间中。

只是一个好奇的问题。还记得在课堂小组作业中，教授会将人们分成一定数量的小组（n）吗？

我的一些教授会从每个学生那里拿出n一份想共事和n不想共事的人的名单，然后神奇地将n学生与他们喜欢并避免与之共事的人配对他们不喜欢的人。

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

编辑：找到一篇 ACM 文章，描述的内容与我的问题完全一样。阅读第二段的似曾相识。

最近我一直在改进多背包问题的传统遗传算法。所以我改进的遗传算法比传统的遗传算法效果更好。我测试过。（我使用从 OR-Library（http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html）公开获得的用于测试 GA。）有人知道其他改进的 GA。我想与其他改进的遗传算法进行比较。其实我在互联网上搜索。但是找不到比较好的算法。

我正在研究背包问题。所以我不明白这里的一件事。

利润/伪资源消耗比

U _j = P _j / W _j其中 W _j = R _ji * A _j

我希望你们知道这个等式，因此我认为不需要更多解释。
我想在这里计算 Aj。那个LP松弛是什么。他们如何使用总容量和重量（物品大小）进行计算。如果我有 n 个项目和 m 个容量，这意味着我应该有 m 个 LP 松弛变量。这样对吗 ？

有人说像

获得相当好的乘数的最简单方法之一是求解线性规划 (LP) 松弛 MKP，其中变量 x _j可以从区间 [0, 1] 中获得任意值，并使用对偶变量的值作为代理乘数。换句话说，a _j被设置为 LP 松弛 MKP 中第 j 个约束的影子价格。

他们如何计算 LP 宽松 MKP 中第 j 个约束的影子价格。我正在从谷歌搜索一段时间，但没有那么清楚。有谁知道通过简单的方式理解？

感谢您阅读到这里:)

如何计算找到这种松弛。我应该知道什么才能找到它。假设我有 n 个物品和 m 个背包。所以我想知道 m 放松的数量。有没有人至少可以给我一些想法。我一直在寻找它。网上有一些文章，但不是很清楚。请至少有人对我说你应该读这个东西，你应该知道这个东西，所以我会非常感激

谢谢

我正在尝试找到计算运输所需包装箱尺寸的最佳方法。

我有 3 个不同尺寸的集装箱。我在数据库中定义了产品的宽度、长度、深度和质量。

我想知道如何找到需要运送的最小数量的盒子，以及考虑到购物车中物品的数量，这些盒子的最小尺寸。

我目前的“想法”是找到整个产品数组的最大宽度，根据它选择一个框，然后根据需要拆分订单……这似乎行不通。

我的盒子尺寸是： - 8 x 6 x 6 = 228 立方英寸 - 10 x 8 x 8 = 640 立方英寸 - 12.5 x 12.5 x 12.5 = 1953.125 立方英寸

产品定义如下：

我研究过背包问题、包装问题等，但找不到解决方法。任何帮助都会很棒。

我一直在使用遗传算法研究背包问题。但是我遇到了一些困难......

首先，用户生成存储在文本文档中的数据集。从那里我将数据读入程序。

我很好地让程序计算适应度值，选择父母，生孩子，然后变异孩子。但由于某种原因，它仅在我人口较少时才有效。当我的人口较少时，我的程序会不断发展，但当我的人口较多时，我的程序就会非常不一致。

例如：当我的人口约为 10-200 时，遗传算法运行完美。但是当我到达更多的人口（大约 300+）时，我会点击运行，但什么也没有发生。然后我重新启动程序并使用相同的数据集，程序成功执行。

我不确定我的代码的哪一部分导致了问题，所以如果您需要一段示例代码，请告诉我您想要哪一部分代码（父选择、加载数据集等）。

多谢！

有谁知道如何使用背包算法实现这个问题的算法？

我目前使用的方法广泛使用了 LINQ 和 Collections of Collections 以及一些字典。对于那些不知道我在说什么的人，请查看切割库存问题。

我不想优化任何东西，而是想列出所有可能的——包括“不完整的”——背包的包装。当然，我可以遍历对象集的所有子集并选择满足权重约束的对象（可以通过设置要查看的子集大小的上限来改进），但我真的想要更多高效的。

谢谢。

我正在尝试解决一个问题（在 php 中，但编程语言无关紧要）。我有n个人支付了钱，我有m个人将支付与n个人支付的总和相同的金额。我想计算这些人之间的最短汇款路线。可以拆分付款并支付给不同的人。理想的情况是一个人只进行一两次交易。有人可以指出我正确的方向或帮助我吗？

示例：A 支付了 100 美元

B 人支付了 200 美元

C 人支付了 50 美元

D 将支付 24 美元

E 人将支付 175 美元

F 人将支付 151 美元

一种可能的解决方案是

E 人向 A 人支付 100 美元，

E 人向 B 人支付 75 美元，

F 人向 B 人支付 125 美元，

F 人向 C 人支付 26 美元

D 人向 C 人支付 24 美元