问题标签 [knapsack-problem]

现在我正在尝试在 Python 3.2 中编写背包问题。我试图用矩阵动态地做到这一点。我尝试使用的算法如下

如果您运行下面的代码，您可以看到它尝试将权重插入列表中。由于这是使用递归，我很难发现问题。我也收到错误消息：无法使用“+”将整数与列表相加。我将矩阵初始化为从第一行和第一列的所有 0 开始，其他所有内容都初始化为 -1。任何帮助都感激不尽。

这是一个典型的背包问题，需要动态规划，并且对物品的供应没有限制。我一直在为我的班级研究这个，我尝试了几个小时的算法，但我仍然没有到达那里。

该方法应该采用 W 和 V 的排序数组，分别包含项目的权重和值，以及表示最大权重的整数 T。对于我的输出，直到 T=21 之前的一切都有效，但是，在那之后它似乎就像一个贪心算法一样工作，这完全不是我所希望的。任何提示将不胜感激，谢谢！

我正在尝试为 01MKP 实施 ACO。我的输入值来自 OR-Library mknap1.txt。根据我的算法，首先我随机选择一个项目。然后我计算构造图上所有其他项目的概率。概率方程取决于信息素水平和启发式信息。

我的信息素矩阵的单元格在初始值 (0.2) 时具有恒定值。出于这个原因，当我试图找到下一个项目时，由于 0.2，pheremon 矩阵变得无效。所以，我的概率函数确定下一个要走的项目，检查启发式信息。如你所知，启发式信息方程是

（Ravg 是资源约束的平均值）。出于这个原因，我的概率。功能选择具有最大利润价值的项目。（假设在第一次迭代中，我的算法随机选择了一个具有 600 利润的项目。然后在第二次迭代中，选择 2400 利润值。但是，在 OR-Library 中，具有 2400 利润值的项目会导致资源违规。无论我做，第二个选择的是有2400利润的项目。

我的算法有什么问题吗？我希望对ACO有所了解的人应该帮助我。提前致谢。

输入值：

我的算法：

在一个项目中我遇到了这个问题，我将在这里用问题的实际领域之外的术语重新表述（我想我可以谈论烟花的口径和形状，但这会使理解更加复杂）。我正在寻找一种（可能是近似的）算法来解决它。

我有n个大小不一的容器，m个不同大小职业、不同颜色的物件（物件可以是多色的，所以一个物件的颜色是真正的一套）。

我的目标是将所有对象放入容器中（我已经知道这是可能的），以便每个容器的颜色种类最小化。对于“颜色的种类被最小化”，我的意思是每个容器的不同颜色数量的总和是最小的。

一个例子。我有两个大小为 2 的容器和四个对象，它们的颜色是 {red}、{red,green}、{blue}、{blue,green}，每个大小为 1。最佳解决方案是 [{red} , {red, green}], [{blue}, {blue, green}]，其中总品种为 2+2=4。更糟糕的解决方案是 [{red}, {blue}], [{red, green}, {blue, green}]，其中总品种为 2+3=5。

我的猜测是这个问题是 NP 难题，因为它听起来比背包问题更难：对象的值被转换为负值，而且取决于同一容器内的其他对象。但是我不知道如何解决这个问题以获得一个近似的解决方案，无论如何这将是非常受欢迎的。

我正在拼命寻找 Java 中的 MCKP 求解器。我需要它来解决这样的拍卖：3 个竞标者，每个竞标者为相同对象的捆绑提供一组报价。假设有 10 件物品要出售，他们可以提供 1、2、3、4 等物品。

显然，每个投标人只能接受一份报价。

所以这显然是一个 MCKP。

谢谢，垫

作为一项家庭作业，我有以下程序要在 java 中制作：

在一个书柜里，我们有一堆 N 本书，这些书必须由 K 个作家手工抄写。每本书都有 Ui 页，其中 Ai 是书。

我们需要从堆栈中给每个作者连续的书，我们不能拆分一本书的页面。

制作一个程序，将书籍提供给作家，但通过最小化作家将复制的最大页数。

作为输入，用户将给出一串数字，其中第一个数字是书籍的数量 N，第二个数字是作者的数量 K，其余的数字是每本书的页数。

作为输出，程序将向用户输出作者将复制的最大页数。

例子：

输入：15 ​​6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
输出：90

在此示例中，第一个作者可以取 book1 = 30 和 book2 = 40，但不能取例如 book1 = 30 和 book3 = 10。换句话说，您只能从堆栈顶部取书，而不会将它们混合在一起。

这是我的实现：

我所做的是每次我将最小的一对书合并在一起，直到我的列表长度等于作者的数量但它不起作用，在示例中而不是 90 它输出 100。

我听说过动态编程解决方案和背包类问题的残酷解决方案，但在我的大学里，他们还没有教我们动态编程，所以教授要么对我们所知道的感到困惑，要么他希望我们找到一个残酷的解决方案。

我确信我的解决方案会起作用，但由于某种原因它不起作用，如果你能在这个或我弄错的地方向我指出另一个解决方案的提示，我会很高兴。

您可以将我指向 DP 解决方案或 Brutal 解决方案，但如果您将我指向 DP 解决方案，请注意我对 DP 实施几乎一无所知。

编辑：我已经看过一些类似背包的问题，​​但我找不到具有这种变化的问题和我能够理解的非 DP 解决方案

您将如何使用动态规划来查找数组中的正整数列表，其总和最接近但不等于某个正整数 K？

我对这个有点卡住了。

我有一个优化问题。这是关于包含 20 个零件的产品（生产顺序无关紧要）。我有 3 台类似的机器，可以生产所有 20 个零件。

我已经得到了以分钟为单位的 20 个部分（即生产第一部分需要 3 分钟，生产第二部分需要 75 分钟，等等）

因此，生产 1 个产品需要 730 分钟。

目的是通过将好的产品分配给三台机器来最小化一种产品的生产。

所以实际上我需要接近 243.333 分钟 (730/3)

可能性很大 3^20

我想有许多不同的最佳解决方案。我希望 R 给我所有这些。我不仅需要知道需要机器 1 2 和 3 的总时间：我还需要知道将哪些物品提供给机器 1、机器 2 和机器 3。

或者，如果它太长，我想选择一个尽可能合理的不重复样本......

我可以用 R 语言解决我的问题吗？

我有一组N数字，每个数字都有一些成本，问题是选择所有可能的数字集作为一个列表，使得它们的乘积小于某个数字M，根据成本总和进行排序。

例如：- 数字集是

并且产品必须小于, Prod <= 1000,

可能的解决方案是： -

所以列表变成了，{Solution2, Solution1}。

PS：-

1. 这不是作业问题，在采访中被问到。我只被问到算法，我只能说它看起来有点类似于背包问题，但用于乘法。
2. 如果我无法正确解释问题，请原谅。

哪种背包问题的算法具有 O(2^n*n) 复杂度？

我被要求为背包问题实施解决方案。

我熟悉编程，但不熟悉渐近符号。

谁能告诉我哪种算法的复杂度为 O(2^n*n)？