问题标签 [knapsack-problem]

我正在尝试编写代码以返回构成给定数字所需的最少硬币数量。我的方法的输入是一组有效硬币，以及我尝试制作的数字。

但是，当我填写以下内容时，这适用于大多数情况：

答案应该是2吧？但它打印出来：

-2147483647

我错过了什么？

我想找到一组加权元素的所有可能组合，其中它们的权重之和恰好等于给定的权重 W

假设我想从集合中选择 k 个元素{ 'A', 'B', 'C', 'D', 'E' }whereweights = {'A':2, 'B':1, 'C':3, 'D':2, 'E':1}和W = 4.

那么这将产生： ('A','B','E') ('A','D') ('B','C') ('B','D','E') ('C','E')

我意识到蛮力的方法是找到给定集合的所有排列（with itertools.permutations）并用 W 的加权和拼接出前 k 个元素。但我正在处理每组至少 20 个元素，这将是计算上的昂贵的。

我认为使用背包的变体会有所帮助，其中只考虑重量（而不是价值）并且重量总和必须等于W（不低于）。

我想在 python 中实现这一点，但任何 cs-theory 提示都会有所帮助。优雅加分！

以下 0-1 背包问题是否可解：

• “浮动”正值和
• 'float' 权重（可以是正数或负数）
• 背包的“浮动”容量 > 0

我平均有 < 10 个项目，所以我正在考虑使用蛮力实现。但是，我想知道是否有更好的方法来做到这一点。

我真的很感激对这个实际问题的一些评论。

快速描述。 我有可变数量的链接，可用于构成给定的皮带宽度。问题是，每个链接有多少。选择标准：最好使用较长的项目。

例子。 假设我们要创建一个皮带宽度，W = 1024.0 其中一个模型具有以下链接长度：L = [34.0, 65.0, 96.0, 126.0]

问题是，每个链接有多少来制作宽度。

这是我尝试过的一些方法。

1.贪婪（选择最长的第一个以满足标准） c = [0,0,0,8] 其中c是每个项目的计数。这留下了 16.0 的差距，我什至无法容纳 1 个最小的项目。贪婪很容易，但并不好。

2. 选择循环 不太容易，我认为这是一个难题。我尝试了很多策略：填充小物品，然后依次移除它们以适应下一个尺寸。

3. 背包法 不太合适，因为这是基于给定数量的物品。

4. 子集和问题 这是背包的一个子类，但我无法让它工作。

5. 装箱问题 听起来很相似，但我无法将其应用于我的问题。

6.蛮力（随机选择） 奇怪的是，这个找到了很多完全匹配。我使用计数的简单多项式作为评级。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... 蛮力的解决方案之一是 [4, 0, 4, 4] 给出正好是 1024。问题是，这种方法通常会产生不同的选择，因此并不理想。

7.穷举搜索 不实用，因为选择太多。

8. 模拟退火 从蛮力的成功来看，这看起来是一个不错的选择。有人可以给我举一个简单的例子吗（请不要是另一个旅行推销员）。

9. 遗传和粒子群 不确定这些。

现在，我陷入困境和沮丧。是否有可用于此问题的直接算法？

样品输出：

注意：在“Turbo C”编译器中编译时，相同的程序会为相同的输入生成合法的输出。

所以这让我相信我没有遵守 C 标准。是这样吗？

就像是

最大重量 3

拿第一个和第三个。但找不到总价值。1955+101。

我使用背包 0-1。有没有从数组中找到 1955+101

问题是如何使用以下信息用贪心算法跟踪背包问题？

如果有人能帮助我理解这一点或指出我正确的方向，我将不胜感激。

在我的代码中，假设C是容量，N是物品的数量，w[j]是物品j的重量，v[j]是物品j的价值，它和0-做的一样吗？ 1 背包算法？我一直在一些数据集上尝试我的代码，似乎是这样。我想知道这是因为我们所学的 0-1 背包算法是二维的，而这是一维的：

这是我对0-1背包算法的实现：（使用相同的变量）

我观看了动态编程 - Kapsack 问题 (YouTube)。但是，我正在解决一个稍微不同的问题，其中约束是预算、价格、双倍而不是整数。所以我想知道如何修改它？Double 是“连续的”，不像整数，我可以有 1,2,3 ...。我不认为我做 0.0,0.1,0.2 ...？

更新 1

我想通过乘以 100 将 double 转换为 int。钱只有 2 个小数位。但这是否意味着值的范围会非常大？

更新 2

我需要解决的问题是：

商品具有价格（双）和满意度（整数）值。我有预算作为约束，我需要最大限度地提高满意度。

在 youtube 视频中，作者创建了两个二维数组，如 int[numItems][possibleCapacity(weight)]。在这里，我不能因为预算是双倍而不是整数

我想解决一个 3 维背包问题。

我得到了许多具有不同宽度、高度、长度和价值的盒子。我有一个指定的空间，我想把盒子放在那个空间里，这样我就能得到最优的利润。我想使用蛮力来做到这一点。

我正在用 Java 编程。我试图用递归来做到这一点，所以：

但我会遇到每行都有不同的自由 x、y 和 z 的问题。

有人可以帮我找到另一种方法吗？