问题标签 [knapsack-problem]

实际上，我已经对这个问题有了部分答案，但我想知道是否可以将这一小段贪婪的代码推广到更接近最佳解决方案的东西。

我是如何遇到这个问题的（与问题本身无关，但可能很有趣）：

我收到了大量的对象（这是一组堤坝的轮廓，每个堤坝沿其长度保持或多或少相同的形状），我可以根据属性（堤坝的名称）对它们进行分组。我的程序输出到一个外部程序，我们必须手动调用它（不要问我为什么），它不能从失败中恢复（一个错误会停止整个批处理）。

在我使用它的应用程序中，对垃圾箱的数量和垃圾箱的最大尺寸没有硬性要求，我尝试做的是

• 保持低组的数量（多次调用程序。）
• 保持较小的集合（如果批次失败，减少损坏）
• 把相似的东西放在一起（一个小组的失败可能是整个小组的失败）。

我没有太多时间，所以我写了一个小贪心函数，将集合组合在一起。

一位同事建议我可以在数据中添加一些噪音来探索我找到的近似解的邻域，我们想知道找到的解离最优还有多远。

并不是说它与原始任务相关，它不需要真正的最佳解决方案，但我想我会与社区分享这个问题，看看它会产生什么评论。

我必须编写 C++ 程序，它将确定我应该使用多少种颜色来为无向图着色。

此外，我必须使用“使用 C++ 伪代码的算法基础”一书中的算法来执行此操作。

问题描述：确定无向图中顶点可以着色的所有方式，只使用m种颜色，使得相邻顶点颜色不一样。

输入：正整数 n 和 m，以及包含 n 个顶点的无向图。该图由一个二维数组 W 表示，其行和列的索引从 1 到 n，其中 W [i] [j] 如果在第 i 个顶点和第 j 个顶点之间存在边，则为真，否则为假.

输出：图的所有可能的颜色，最多使用 m 种颜色，因此没有两个相邻的顶点颜色相同。每个着色的输出是一个从 1 到 n 索引的数组 vcolor，其中 vcolor [i] 是分配给第 i 个顶点的颜色（1 到 m 之间的整数）。

我们有算法：

最后评论：按照我们通常的约定，n、m、W 和 vcolor 不是任何例程的输入。在算法的实现中，例程将在一个简单的过程中本地定义，其中 n、m 和 W 作为输入，并且 vcolor 在本地定义。对 m_coloring 的顶级调用是m_coloring( 0 )

我开始编写自己的实现。首先我想说，我不是一个优秀的 C++ 程序员，而且，我通常使用 JS 和 PHP，弱类型语言，所以我确信还有很多事情我可以做得更好。但这不是主要问题。

问题是：上面的程序开始工作，我写了简单的图：

4 个顶点，4 条边

1 2
1 3 2 3 3 4

接下来，程序开始使用checkFor()（我计划在 for() 中使用它来处理下一个颜色，但出于测试目的，我以静态方式使用它，所以我使用了 4。

不幸的是，程序启动 m_coloring()，下一次启动 promise() 并且......这就是结束。我花了最后三个小时来找出我做错了什么，也许任何更有经验的程序员能够解释我应该做什么和/或我做错了什么......

请帮忙，非常感谢。

我的程序代码：

我想用动态规划解决背包问题！该物品是否应该在背包中，我不想将相同的物品放在背包中超过一次！

我已经查看了这段代码，但是使用这段代码，您可以多次添加相同的对象而不是一次

然后我尝试创建一个数组以查看该对象是否在背包中，但是该程序没有正常工作！

你们能帮帮我吗？:)

我正在尝试以最少的掉落或浪费嵌套材料。

我已经研究过贪婪算法、装箱、背包、1D-CSP、分支定界、蛮力等。我很确定这是一个切割库存问题。我只需要帮助想出运行它的功能。我不仅有一个库存长度，而且有多个，用户可以输入他自己的不太常见长度的库存。任何帮助确定要在 PHP 中使用的函数或算法以提出优化的切割模式和所需的库存长度，并且浪费最少，我们将不胜感激。

谢谢

我有一个问题如下：

1. 我几乎没有具有不同功能（整数）的办公地点和资源。
2. 我想将所有资源分配到不同的办公地点，以找到将它们几乎平均分配到不同地点的最佳方式，以便尽可能平衡所有办公地点的能力。要记住几件事：

• 每个办公地点的资源数量差异不应超过一个。• 每个办公地点的能力（通过增加个人能力来达到）应该尽可能地彼此相等。

我通过互联网进行了研究，并了解了听起来接近这个问题的背包算法和 Bin-pack 算法。

示例：办公地点数量 = 3；人数=8；人员能力 = 10、20、5、150、90、200、250、140（8 种资源的能力值）；

以上数字只是样本。对于资源和各自的能力价值，它可以增长到 1000+。办公地点的数量也可以变化。

我没有开始编程部分，除非我确定我要走的路是正确的。我请求您的帮助来指导我找到正确的方向来解决这个问题。

此外，如果您可以为此共享一个可能的伪代码，那将是一个很大的帮助。

谢谢！

我正在尝试开发一种算法来从更大的列表中选择活动的子集。如果选中，每个活动都会使用一定数量的固定资源（即所选活动的总和必须保持在总预算之下）。可能有多个可行子集，从中选择的方法将基于计算未选择活动的机会成本。

编辑：这不是0-1 背包问题有两个原因：

• 背包需要整数值作为重量（即消耗的资源），而我的资源消耗（即背包用语中的质量）是一个连续变量。（显然，可以选择某种程度的精度并量化所需的资源，但我的 bin 大小必须非常小，并且 KnapsackO(2^n)在 W 中。
• 我无法先验地计算机会成本；也就是说，我不能独立评估每个人的适合度，尽管我可以评估给定一组选定活动的效用或向现有列表添加额外任务的边际效用。

我所做的研究表明了一种幼稚的方法：

定义幂集
对于幂集的每个元素，根据不在集合中的项目计算它的效用
选择效用最高的元素

但是，我知道有一些方法可以加快执行时间和所需的内存。例如：

• 完全枚举 powerset 是O(2^n)，但我不需要完全枚举列表，因为一旦我发现一组超出预算的任务，我知道任何添加更多任务的集合都是不可行的并且可以被拒绝。也就是说，如果{1,2,3,4}是不可行的，那么是不可行的{1,2,3,4} U {n}，其中 n 是剩余在较大列表中的任何一项任务。
• 由于我只是在总结职责，因此任务的顺序并不重要（即，如果{1,2,3}可行，那么{2,1,3},{3,2,1}等）。
• 最后我需要的只是选定的集合，所以我可能只需要迄今为止找到的最佳效用值来进行比较。
• 我不需要保留列表枚举，只要我可以确定我已经查看了所有可行的枚举。（尽管我认为保留先前计算的可行子集的占空比可能会加快运行时间。）

我已经说服自己一个好的递归算法会起作用，但我不知道如何定义它，即使是在伪代码中（这可能是最有意义的，因为它将用几种语言实现——可能Matlab 用于原型设计，然后是编译语言）。

我有一个从 0 到 3 的 5x5 值表，所有值都未知。我知道每行和每列的值的总和和零的数量。我将如何使用 C# 解决这个 0-1 背包问题并检索满足已知和和零数的可能解决方案？桌子总是五行五列，所以它不是一个传统的背包。

例如，假设我们输入：

我们会将此作为可能的解决方案：

在这种相当奇怪的情况下，我应该采用什么类型的算法？我是否还必须编写一个类来枚举排列？

编辑澄清：问题不在于我无法列举可能性；那是我不知道如何有效地确定添加到任意总和的排列，同时包含指定数量的零和最多 5 个项目。

以下问题：

我有一个 MySQL 数据库，里面有歌曲。该数据库具有以下结构：

用户应该能够在 php 表单中输入特定时间，并且 php 函数应该为他提供所有可能的歌曲组合列表，这些组合加起来等于给定时间 ±X 分钟。

因此，如果用户想听 1 小时 ±5 分钟的音乐，他会在表格中输入 60 分钟和 5 分钟的阈值，并会收到所有可能的歌曲集，总时长为 55 到 65 分钟。它不应该打印出重复项。

我已经找到了解决这个问题的几种方法，但它们只给了我加起来为 X 的持续时间，而不是歌曲名称等。所以我的问题是如何解决这个问题，以便它给我返回添加的歌曲的 ID到所需的时间或打印出带有相应歌曲名称的列表。

这似乎是我找到的最佳答案之一，但我无法将其适应我的数据库。

这是一个有趣的项目，我已经开始尝试并最大限度地提高赢得办公室曲棍球池的机会。我正在尝试找到最好的方法来选择 20 名球员，这些球员将在最高工资帽内给我最多的分数。

例如，假设原始数据由

1. 玩家名称
2. 位置（前锋、后卫、守门员）
3. 本赛季预测积分
4. 薪水。

现在我想要在 X 工资帽内给我最高分的 20 名球员。稍后，作为第 2 阶段，我想做同样的事情，但在这种情况下，我只想要 12 名前锋、6 名后卫和 2 名守门员。

现在显而易见的方法是简单地使用所有可能的组合，但是虽然这会起作用，但它不是一个有效的选项，因为有 500 名玩家，这将有太多可能的组合。我可以添加一些智能过滤器，将 500 名球员减少到前 50 名前锋、前 30 名后卫和前 15 名守门员，但这仍然是一个非常缓慢的过程。

我想知道是否还有其他算法可以实现这一点。这只是为了好玩，而不是重要的业务请求。但是，如果您对如何进行有一些想法，请告诉我。

我的第一次尝试是在其他来源的帮助下使用背包算法。它似乎只使用薪水作为参数。我正在努力弄清楚如何添加 20 人团队参数。它在 .Net 中，但应该很容易转换为 Java。

我正在考虑做一个单独的循环来找出拥有 20 名球员且不计薪水的最佳球队，然后比较这两个列表，直到我找到两个列表中最高的球队。没有把握。

谢谢你的帮助！

我基于此处的伪 Java 代码编写了分支定界背包算法的实现。不幸的是，像这样的问题的大型实例会导致内存阻塞。为什么是这样？我怎样才能使这个实现更有效率？

链接上文件的输入格式如下：

}