这个问题是否可以在多项式时间（或伪多项式时间）内解决？

Question

我正在尝试设计一个合理的算法来解决这个问题：

假设您有一堆球。每个球至少有一种颜色，但也可以是多彩的。每个球都有一个重量和一个与之关联的价值。还有一堆盒子，它们各自只有一种颜色。每个盒子都有一个最大的装载球数。目标是在保持总重量不超过W的情况下最大化盒子中的总价值，唯一的规则是：

为了将一颗球放入盒子中，它必须至少具有盒子的颜色。

（例如，您可以将蓝色和绿色的球放入蓝色或绿色的盒子中，但不能放入红色的盒子中。）

我已经进行了一些研究，发现这似乎类似于背包问题，也类似于可以通过匈牙利算法解决，但我似乎无法将其简化为任何一个问题。

我只是好奇是否存在某种动态规划算法，使得这种类型的问题可以在多项式时间内得到解决，或者它只是旅行推销员问题的伪装。如果我知道最多有X种颜色，是否有帮助？非常感谢任何帮助。如果需要，我还可以使用变量名来规范化问题。谢谢！

这里是一个简单的例子：

最大重量：5

球：

1个红球 - （价值= 5，重量= 1）

1个蓝色球 - （价值= 3，重量= 1）

1个绿色/红色/蓝色球 - （价值= 2，重量= 4）

1个绿色/蓝色球 - （价值= 4，重量= 1）

1个红色/蓝色球 - （价值= 1，重量= 1）

盒子：

1个红色（容纳1个球）

1个蓝色（可容纳2个球）

1个绿色（容纳1个球）

最佳解决方案：

将红球放入红盒中

蓝盒中的蓝球和红/蓝球

绿盒中的绿/蓝球

总价值：13（5 + 3 + 1 + 4）

总重量：4（1 + 1 + 1 + 1）

注：尽管绿/红/蓝球比红/蓝球更有价值，但它的重量会使我们超过限制。

编辑：

一个澄清的点：具有相同颜色组合的球不一定具有相同的重量和价值。例如，你可以有一个价值为3、重量为1的红球，和一个价值为2、重量为5的红球。

编辑2：

如果这样做有助于我们提出动态编程算法，那么我们可以假设整数权重和价值。

- Kenny

---

@Voo：你能帮我看看这个怎么转化成背包问题吗？每个箱子似乎都是一种背包，但每个箱子有一个容量限制而不是重量限制，而我需要在最大化价值的同时保持总重量在一定范围内。 - Kenny

@Kenny，这只是假设球可以有任意重量，如果是这样的话 - 已经回答的人的解释与我给出的解释相同。 - Voo

为了在多项式时间内解决问题，您必须能够处理该问题的所有实例。容量限制的添加并不重要，因为您可以将问题设置为具有非常高的容量限制，以至于它不相关（例如，将其设置为球的总数）。 - comingstorm

换句话说：增加容量限制可能会使背包问题更难，但它无法使其变得更容易。 - comingstorm

我想我原本希望有一个“伪多项式时间”解决方案。我应该澄清一下。显然，这个问题至少和背包问题一样复杂。 - Kenny

Answer 1

这至少和背包问题一样复杂 - 考虑所有球都是红色且只有一个红盒子的情况。

当颜色组合相同的球具有相同的重量和价值时，考虑一种情况，即你有红/蓝、红/绿等球和只有一个红盒子。

- Paweł Obrok

---

没错 +1。然而，球的多彩特性可能会使通常的动态编程解决方案变得更加复杂。 - Voo

澄清一下：具有相同颜色组合的球不一定具有相同的重量和价值。例如，您可以拥有一个价值为3，重量为1的红色球，以及另一个价值为2，重量为5的红色球。 - Kenny

无论如何 - 您可以使用此问题表示背包的任何实例，因此它是NP难问题。 - Paweł Obrok

其实它是伪多项式 - 这意味着在这种情况下，它是权重总和的多项式 - 即使对于小问题，它可能非常大！对于这个问题来说，有效的动态算法不太可能存在 - 状态非常复杂 - 每种球和盒子都必须单独处理，因此搜索树中的节点不太可能重复。 - Paweł Obrok

@Kenny 这个证明并不能排除动态规划解决方案（伪多项式时间）的可能性。背包问题是弱NP完全的。要完全证明这种不存在性，我们必须将一个强NP完全问题通过一些额外的要求归约到它上面。 - aelguindy

Answer 2

如果箱子数量没有限制，那么这个问题通过从3-partition（设置n/3个箱子，并使所有物品彩虹色，价值=重量）进行规约，是强NP难问题。

如果箱子数量是固定的，则可以通过动态规划实现伪多项式时间算法，其中每个DP状态包括每个箱子的填充情况。

- junction

---

你能详细说明一下，假设箱子数量是恒定的，这个DP算法将如何工作吗？谢谢！ - Kenny

逐一考虑每个物品。在每个步骤中，保持一个由元组索引的表格，描述每个盒子的装满程度。例如，索引（2,2,3）表示第一个盒子有2个物品单位，第二个盒子也是2个，第三个盒子是3个。每个表格条目是到目前为止考虑的物品中可以获得的最大值，使得每个盒子都填充到该条目的索引指定的水平。 - junction

Answer 3

减少背包问题的方法如下。给定您的背包实例，您创建一个球和箱子问题的实例：对于背包实例中的每个物品，您都有一个具有与该物品相同重量和价值的球。然后您有一个代表背包的盒子。球和盒子都是蓝色的。盒子的容量是背包问题中给定的限制。给定解决方案，我们在盒子中有一组球，其总重量最多为背包限制，并且其总价值最大化。

- Irit Katriel

Answer 4

这个问题是NP完全问题，因为它包含了背包问题。

也就是说，这不仅仅类似于背包问题：如果只有一个碗，所有的球都有相同的颜色，并且碗中最多可以放置的球数等于所有球的总数，那么问题就变成了背包问题。

如果一个算法能够在多项式时间内解决这个问题，它就能够在多项式时间内解决任何背包问题。但是，由于背包问题是NP完全问题，所以这个问题也是NP完全问题。

- comingstorm

---

我同意使用一个盒子时，这就变成了背包问题，但我不知道如何使用相同的技术来解决存在多个具有不同颜色的盒子的问题。由于球可以有多种颜色，它们可能适合不同的盒子，因此单独的“背包”并不是独立的。 - Kenny

你的问题是“是否可以在多项式时间内解决问题”。这是最坏情况：如果你能组合出任何可能无法在多项式时间内解决的问题，那么答案是“否”。另一种表述方式是：如果你找到了一个能够在多项式时间内解决这个问题的算法，那么你已经证明了P=NP。虽然我们并不确定这是不可能的，但看起来不太可能... - comingstorm

谢谢，我应该早点澄清：我希望也可能/实际上有一个“伪多项式”解决方案。 - Kenny

Answer 5

在这种情况下，你所能做的最好的事情就是得到最优解的近似值——背包问题本身不可能在多项式时间内求解。如果你能为它生成一个好的算法，你仍然可以在多项式时间内得到良好的（虽然不保证是最优的）结果。

- Mikey