有没有适用于有界0-1多重背包的伪多项式算法？
假设有n个物品，例如i1,i2, .... in，它们每一个都有已知的有界重量w1,w2,...wn。还有一组m个背包，例如k1,k2和km。这些背包是同质的，即它们都具有相同的容量W。函数F可以确定每个背包的分数。F的输入是每个背包中的物品。因此，Score of each knapsack...
奇怪但实用的二维装箱优化
我正在尝试编写一个应用程序，为分隔面板生成绘图。 我有N个小隔间（2D矩形）（N 这些N个隔间必须按列排列，以便满足每个隔间的上述约束条件。 此外，每列的宽度由该列中每个隔间的minWidths的最大值决定。 此外，每列的高度应相同。 这决定了面板的高度。 我们可以在任何列的剩余空间中添加...
多背包问题中，物品只有重量，如何解决？
我正在尝试解决这个问题，并想知道是否有已知的算法/解决方案可以解决这个问题。 问题： 我有n个袋子和n个物品（它们的重量可能相等也可能不同）需要放入这些袋子中。每个袋子都有一定的重量限制，并且需要以这样的方式将n个物品放入这些袋子中，以便我可以在每个袋子中使用最大的空间。 袋子大...
算法设计：您能提供多背包问题的解决方案吗？
我正在寻找一种伪代码解决方案，来解决多背包问题（优化语句在页面中间）。我认为这个问题是NP完全问题，所以解决方案不需要是最优的，如果它相当高效和易于实现那就好了。 问题如下： 我有很多工作项，每个工作项需要不同（但固定和已知）的时间完成。 我需要将这些工作项分成组，以便具有最小的组数（理...
底部动态规划可以在Lisp中实现吗？
一个典型的Lisp方言能够使用自底向上的动态规划方法解决问题吗？ （请注意：我不是在谈论“记忆化”，据我所知，使用任何Lisp方言都很容易实现。我真正说的是自底向上的动态规划，其中您从下往上构建数组，然后使用您刚刚引入的元素来计算下一个元素。） 例如，使用动态规划，“0-1背包”问题可以在...
将人分成团队以获得最大的满足感。
一个好奇的问题。还记得那些在课堂小组作业时，教授会将人们分成固定数量(n)的小组吗？ 我的一些教授会从每个学生那里获取一个希望合作的n人名单和一个不想与之合作的n人名单，然后神奇地组成n人的小组，让学生与他们喜欢的人匹配，并避免与他们不喜欢的人一起工作。 对我来说，这个算法听起来很像一个背...
为什么解决背包问题不被视为线性规划？
尽管背包问题看起来与线性规划问题相似，为什么背包问题没有被归类为线性规划算法的一种呢？
背包问题中的物品分组问题
显然在Stack Overflow上不能称之为问题，但我目前正在尝试理解如何将项目组的约束条件整合到背包问题中。在这种情况下，我的数学技能似乎相当有限，但我非常有动力让它按预期工作，并找出每个方面的作用（按照这个顺序，因为当事物工作时，它们更有意义）。 话虽如此，我在Rosetta Code...
动态0/1背包问题是个笑话吗？
我已经得到了一项证据，可以证明关于0/1背包问题的一个普遍看法是错误的。我真的很难相信自己是对的，因为我找不到任何地方支持我的说法。因此，我将首先陈述我的说法，然后证明它们，我希望任何人都能进一步证实或证伪我的说法。感谢任何合作。 说法： 解决背包问题的bnb（分支定界）算法的规模不会与K（...
背包问题：如何将物品类型添加到现有解决方案中
我一直在使用这个变式的动态规划算法来解决背包问题:KnapsackItem = Struct.new(:name, :cost, :value) KnapsackProblem = Struct.new(:items, :max_cost) def dynamic_programming_...