问题标签 [knapsack-problem]

我遇到的问题如下：
假设我有一个给定重量的存钱罐，我正在用一组给定的硬币存钱。最后，我知道了存钱罐的总重量以及我使用的硬币的重量和价值。

我想找出我可以保证存入存钱罐的最低金额，即最坏的情况。例如，如果：

• 总重量 = 100
• 使用的硬币重量 = {1, 50}
• 硬币的价值 = {1, 30}

那么我可以保证的银行最低值是60。

问题是背包变体，但我无法找到正确的重复出现。

提前致谢！

好吧，这是一个古老的 0-1 背包问题，但在找到我能得到的最高总价后，我需要找到我可以携带的物品。但是对于以下测试用例（共3项）

这里的最高价格是 5。但对于重量，它可以是6或10(5+5)。两者都会给出相同的价格，但显然可行的是 6 公斤的物品而不是 10 公斤的物品。我想提示我如何从 dp 矩阵计算这个。我得到了这个测试用例的以下矩阵。

使用这个算法，它发现重量为 10，但最佳重量为 6 公斤。

我是动态编程的新手，并在 SPOJ (http://www.spoj.pl/problems/KNAPSACK/ ) 尝试过整数背包问题。但是，对于给定的测试用例，我的解决方案没有给出正确的输出。如果您能建议我的以下实施是否正确，我将不胜感激。请注意，该变量back用于回溯，我不知道该怎么做。我也希望在实施回溯方面得到您的帮助。谢谢。

以下是正确的输入/输出测试用例：

但是，我得到的输出是17.

我必须实现一个有约束的 0/1 背包问题的解决方案。在大多数情况下，我的问题几乎没有变量（〜 10-20，最多 50）。

我记得在大学里有许多算法在许多情况下比蛮力执行得更好（例如，我在想分支定界算法）。

由于我的问题相对较小，我想知道在使用复杂的解决方案而不是蛮力时在效率方面是否有明显的优势。

如果有帮助，我正在用 Python 编程。

我是动态编程的新手，并尝试了我的第一个 DP 问题。问题陈述是

给定一个大小为 C 的背包和 n 个大小为 s[] 且值为 v[] 的物品，最大化可放入背包的物品的容量。一个项目可以重复任意次数。（允许重复项目）。

虽然我能够制定递归关系并创建 DP 表，并最终获得可以放入背包的最大值，但我无法设计一种方法来检索必须选择哪些值才能获得所需的总和.

这是我的解决方案：

在我的解决方案中，我尝试将选择的最大值项的位置存储在向量中，并最终打印出来。然而，这似乎并没有给我正确的解决方案。

运行程序会产生：

从输出中可以明显看出，输出中的数字不能是所选项目的大小，因为输出中没有大小为 0 的项目。

我希望你能帮助我找到我的逻辑或实现中的错误。谢谢。

我有一个预定大小的二维数组和一个适合该空间的编号矩形列表。这些矩形中的每一个都具有已知的固定高度和宽度。保证 2D 阵列足够大以舒适地适应所有矩形。

我需要将这些矩形中的每一个随机放置到数组中，以便没有重叠并且全部放置。它们可以放置在任何方向。想象一下，将您的船只置于战舰游戏中，只是拥有更多不同的船只尺寸和更大的网格。

完成后的数组应该是这样的：（0代表一个空格，一个非零数字代表一个矩形数字）

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 0 0 0 0 0
0 0 0 2 2 2 2 0 0 0 0 0 0 0 0
0 0 0 2 2 2 2 2 0 5 5 0 0 0 0
0 3 3 3 3 3 0 0 0 0 5 5 0 0 0 0
0 3 3 3 3 3 0 7 7 7 5 5 6 6 0 0
0 0 0 0 0 0 0 7 7 7 5 5 6 6 0 0

我考虑过的一种方法是为每个矩形选择一个随机的位置和方向，尝试将其放置在矩阵中。如果检测到与先前放置的块发生冲突，请重试。这可能是最简单的实现，但它似乎不是很有效，并且它不会以明确确定的方式终止（列表末尾附近的矩形可能会在很长一段时间内与先前生成的块发生冲突）。

有没有更好的方法来解决这个问题，放置后面的矩形不会那么成问题？

我遇到了一个问题，我会尽量用最简单的术语来描述它。

使用 PHP 和 MySQL 的组合我需要完成以下逻辑问题，这是所需内容的简化版本，但简而言之，逻辑是相同的。

思考框。我有很多小盒子，一个大盒子。我需要能够使用许多小盒子来填充大盒子。

所以让我们分解一下。

我在 MySQL 中有一个表，其中包含以下行

这张桌子可以多达数百个，有些盒子的大小相同

我现在需要填充一个大小为 800 的大盒子，其中包含我在表中找到的所有 small_boxes 组合。大框可以是用户希望填充的任何大小。

这里的目标不是效率，例如，我并不真正关心稍微低于或略高于，只是在公差数字内显示可能适合的盒子的不同变化。

所以如果可能的话，我想了解如何在 PHP/MySQL 中解决这个问题。我在这两方面都很有能力，但问题在于我如何处理这个问题。

例子会很棒，但我很乐意接受一些信息来帮助我开始。

我正在寻找多/多目标子集和问题的快速解决方案。

作为额外的限制（这使得 IMO 更容易计算），我们可以假设总和中包含的所有值都是正的，并且都绑定到一个已知的极限值。

我知道单目标子集和问题有一个 O(NK) 伪多项式解决方案，我已经实现了一个基于维基百科和这个堆栈交换答案的解决方案。

以其他方式解释这个问题，我有两组已知限制的正数。对于第一组中的每个值 A，第二组中的值的组合总和为 A。先验地知道第一组中的所有值具有对应的且不冲突的第二组中关联的值组合，是有一种已知的快速方法来计算第二组中的哪些元素与每个第一组值相关联？

我有一组大小为 n 的数字（假设 n > 100）。

我也有一个硬限制 x。

我想要的是从我的集合中获取可变数量的元素并找到这些元素的组合，以便在相加时总和为 <= x，但尽可能接近 x。

显然我不想采用蛮力方法，有没有一种有效的算法可以解决这个问题？

我正在尝试使用分支和边界来实现这个背包问题的 C++ 实现。这个网站上有一个Java版本：Implementing branch and bound for knapsack

我试图让我的 C++ 版本打印出它应该打印出的 90，但它没有这样做，而是打印出 5。

有谁知道问题可能出在哪里和什么地方？