问题标签 [np-complete]

我有一个集合 I ={P1, P2, ..., Pm} 和 I 的 n 个有限子集，用 R1,R2,...,Rn 表示，如下所示：

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2，P3，P4}

R4 = {P1，P2，P4}

……

其中 Pi 表示一个整数。

对于每个 Ri，我想计算其所有元素的乘积。我的目标是通过在 Ri (i=1,2,...,n) 之间共享一些公共部分来尽可能少地使用乘法和除法。

例如，如果我可以先计算 P2*P4，那么这个结果可以用于计算 R3 和 R4 的所有元素的乘积。

请注意，也允许除法。例如，我可以先计算 A=P1*P2*P3*P4，然后使用 A/P1 计算 R3 的所有元素的乘积，然后使用 A/P3 计算 R4。

如果我想使用最小乘法和除法来计算 I 的每个子集的所有产品，这是一个集合覆盖问题吗？NP完全？顺便说一句，您能否给出一个整数线性程序公式来描述它，就像这里一样。

任何建议将不胜感激！

社区编辑：附加假设：

• 允许除法，与乘法相同的成本
• 给定集合中没有重复的元素。例如R5 = {P1, P1, P1, P2}不允许

相关问题：

• 将数字列表划分为2个相等总和列表的算法
• 将列表分成两部分，它们的总和彼此最接近

假设我有一个列表，其中包含确切的2k元素。现在，我愿意将它分成两部分，其中每个部分的长度为 ，k同时试图使各部分的总和尽可能相等。

快速示例： [3, 4, 4, 1, 2, 1]可能会拆分为[1, 4, 3] and [1, 2, 4]，总和差将是1

现在 - 如果部分可以有任意长度，这是分区问题的变体，我们知道这是弱NP-Complete.

但是关于将列表分成相等部分的限制（假设它总是kand 2k）是否使这个问题可以在多项式时间内解决？任何证明（或证明它仍然存在的证明方案NP）？

我的问题类似于这里的问题https://cs.stackexchange.com/questions/2244/need-a-np-complete-proof-on-an-example，但有点不同。

这是我的问题：

有A、B、C三个岛，还有很多扇形的木筏。我们必须从 A-->B-->C 建造一座桥，并且每个部分所需的筏板数量是已知的，例如，连接 AB 需要四个筏板，连接 BC 需要三个筏板。

这些木筏原本在不同的位置，它们可以免费旋转。有趣的是，如果需要，它们可以相互重叠。移动一个筏板的距离可以计算为质心原始位置与其展开位置之间的距离。

目标是找到具有移动筏的最小总距离的解决方案，以使桥梁 A-->B-->C 并使用桥梁每个部分的确切筏数。

我习惯用下图来说明我的问题。

从这个图中我们可以看出，排列可能不是一条直线，木筏可以与另一个木筏重叠。

这些筏子的候选位置太多了。看来问题是NPC。我不知道我是否正确以及如何证明它是NPC。有谁知道如何解决它？谢谢！

0-1 背包问题被称为 NP 完全问题。但是如果每个项目的权重相同，那么问题仍然是 NP 完全的吗？

给定一个无向图 G=(V,E)，每条边都与一个非负值相关联。

如何在图 G 上找到从 s 到 t 的顶点不相交路径的最大数量，约束条件是路径长度之和不大于预定义值 T。

假设我们有多个由 Length x Width 定义的箱尺寸，这些可以称为“原材料”尺寸。

我需要从该原材料中切出一定数量的表格（矩形，断头台形式），以最大限度地减少原材料的数量。

由于垃圾箱的大小不同，它们应该以某种方式考虑或优先考虑以反映它们的价值 - 所以更大的垃圾箱显然“更贵”。

我知道这是一个 NP 完全问题，我不希望在多项式时间内出现确定性算法。

我需要一个解决问题的算法。

任何的意见都将会有帮助！

谢谢

我有一些容量不同的垃圾箱和一些指定大小的对象。目标是将这些对象打包到垃圾箱中。到目前为止，它类似于装箱问题。但扭曲的是，每个对象都与另一个对象有部分重叠。因此，虽然对象 1 和 2 的大小分别为 s1 和 s2，但当我将它们放在同一个 bin 中时，填充的空间小于 s1+s2。假设我知道每对对象的重叠值，是否也有任何近似算法，例如用于该问题的原始装箱算法？

我有一个图 G=(V,E) 边和节点都有权重。我想对该图进行分区以创建大小相等的分区。分区大小的定义是 sum(vi)-sum(ej)，其中 vi 是该分区内的一个节点，ej 是该分区内两个节点之间的一条边。在我的问题中，图表非常密集（几乎完整）。是否有任何近似算法？

这在某种程度上类似于 bin 包装中的问题，其中 bin 具有相同大小的重叠对象。节点的权重是它们的大小，边的权重显示两个对象可以重叠多少。

有一个城镇网络，由各种整数长度的道路连接。

一位旅行者希望开车从一个城镇到另一个城镇。但是，他不想最小化行驶的距离；相反，他希望尽量减少旅途中的汽油费用。汽油可以在任何城市购买，但是每个城市以不同的（整数）价格供应汽油（因此为什么最短的路线不一定是最便宜的）。1 个单位的汽油使他能够行驶 1 个单位的距离。他的车只能在油箱里装这么多汽油，他可以选择在他所经过的每个城市购买多少单位的汽油。找出最低的汽油成本。

有谁知道可以用来解决这个问题的有效算法？即使是这类问题的名称也会很有用，这样我就可以自己研究了！显然，它与最短路径问题并不完全相同。任何其他提示表示赞赏！

编辑-我遇到的实际问题表明将有<1000个城市；<10000 条道路；油箱容量将在 1 到 100 之间。

我无法理解图形着色的 NP 完整性。

如果我假设使用 DFS 的贪婪着色策略（http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring），那么我似乎能够以最佳方式为图形着色。谁能帮我举个反例？

为了清楚起见，让所有节点都被着色为-1。为起始节点着色 1. 继续进行 DFS 遍历，用尚未分配给其邻居的最小整数为每个节点着色。什么时候无法为图形优化着色？