问题标签 [np]

Wiki 说，当您将 poly time 中的 np 完成问题转换为 A 时， A 是 np 困难的。见http://en.wikipedia.org/wiki/NP-hard

但是下面的 pdf 说，当您在多项式时间内将 np 难题转换为问题 A 时，A 是 np - hard http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard。 pdf

我应该相信哪一个？

I'm trying to come up with a reasonable algorithm for this problem:

Let's say you have a bunch of balls. Each ball has at least one color, but can also be multicolored. Each ball has a weight and a value associated with it. There are also a bunch of boxes which are each only one color. Each box has a maximum number of balls it can hold. The goal is to maximize the sum of the value in the boxes while staying under some total weight, W, and the only rule is:

In order to place a ball in a box, it has to at least have the box's color on it

(For example, you can put a blue and green ball into a blue box or a green box, but not into a red box.)

I've dome some research and this seems similar to the knapsack problem and also similar to being solvable by the Hungarian algorithm, but I can't quite seem to reduce it to either problem.

I'm just curious is there's some kind of dynamic programming algorithm for this type of problem to make it solvable in polynomial time, or if it's just the traveling salesman problem in disguise. Would it help if I knew there were at most X colors? Any help is greatly appreciated. I could also formalize the problem a bit with variable names if it would help. Thanks!

Here's a simple example:

Maximum weight: 5

Balls:

1 red ball - (value = 5, weight = 1)

1 blue ball - (value = 3, weight = 1)

1 green/red/blue ball - (value = 2, weight = 4)

1 green/blue ball - (value = 4, weight = 1)

1 red/blue ball - (value = 1, weight = 1)

Boxes:

1 red (holds 1 ball)

1 blue (holds 2 balls)

1 green (holds 1 ball)

Optimal Solution:

red ball in red box

blue ball and red/blue ball in blue box

green/blue ball in green box

Total value: 13 (5 + 3 + 1 + 4)

Total weight: 4 (1 + 1 + 1 + 1)

Note: even though the green/red/blue ball was more valuable than the red/blue ball, it's weight would have put us over the limit.

Edit:

One clarifying point: balls with the same color combination will not necessarily have the same weights and values. For example, you could have a red ball with value 3 and weight 1 and another red ball with value 2 and weight 5.

Edit 2:

We can assume integer weights and values if it helps us come up with a dynamic programming algorithm.

在一个项目中我遇到了这个问题，我将在这里用问题的实际领域之外的术语重新表述（我想我可以谈论烟花的口径和形状，但这会使理解更加复杂）。我正在寻找一种（可能是近似的）算法来解决它。

我有n个大小不一的容器，m个不同大小职业、不同颜色的物件（物件可以是多色的，所以一个物件的颜色是真正的一套）。

我的目标是将所有对象放入容器中（我已经知道这是可能的），以便每个容器的颜色种类最小化。对于“颜色的种类被最小化”，我的意思是每个容器的不同颜色数量的总和是最小的。

一个例子。我有两个大小为 2 的容器和四个对象，它们的颜色是 {red}、{red,green}、{blue}、{blue,green}，每个大小为 1。最佳解决方案是 [{red} , {red, green}], [{blue}, {blue, green}]，其中总品种为 2+2=4。更糟糕的解决方案是 [{red}, {blue}], [{red, green}, {blue, green}]，其中总品种为 2+3=5。

我的猜测是这个问题是 NP 难题，因为它听起来比背包问题更难：对象的值被转换为负值，而且取决于同一容器内的其他对象。但是我不知道如何解决这个问题以获得一个近似的解决方案，无论如何这将是非常受欢迎的。

输入：n个元素的M个有序元组的集合，其中每个元素都是一个集合，即：(A1, A2, ..., An)，其中每个Ai都是一个集合

问题：将这些 n 元组组合在一起以创建最小的 n 元组集合。如果它们仅在一个位置不同，则可以将 2 个 n 元组组合在一起，即：

A = (A1, A2, ..., An) 和 B = (B1, B2, ..., Bn) 可以组合成 (A1, A2, ..., Ai U Bi, Ai+1, ... ., An) 当且仅当 Aj = Bj，对于每个 j != i。

示例： 输入：4 个 2 元组：({1}, {1}), ({1}, {2}), ({3}, {1}), ({3}, {2}) 输出: 一个 2 元组: ({1, 3}, {1, 2})

我的问题是：你将如何解决这个问题？你知道它是否可以简化为一个已知的 NP 问题吗？一个想法是将其建模为图形：如果元组 A 和 B 可以组合，则在它们之间用颜色 i 绘制一条彩色边（i = 它们不同的位置）。

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

我正在为一家航空运输公司做一些行政工作。他们在这里建造飞机集装箱等。他们希望我编写的其中一件事是一个订单优化脚本，在场的人可以使用它来充分利用给定的材料。给出一个简单的概述：假设我们订购了一定数量的每单位 10 米的梁。我们需要 5x 6m、10x 3.5m、4x 3m 的梁块，它们是通过将 10m 切割成更小的部分来获得的。我们需要订购的 10m 光束的最小数量是多少？

与多处理器作业调度问题有一些相似之处（一个梁是一个处理器，每个块都是一个作业），尽管它侧重于最小化执行所有作业所需的时间，而不是最小化执行所有作业所需的处理器数量。 -设置时间。多处理器作业调度问题是 NP 完全的，但我想知道我对问题的变体是否也是。有没有人知道类似的问题和解决方法？

我有 80 个节点，我需要从中找到一个长度为 40 的循环，同时将循环经过的距离保持在最小。有些节点不能直接连接，它们在特定区域，我只能从一个区域到另一个区域，而不是在一个区域内。

我只是在这里一般性地问，我可以使用什么样的技术来获得 40 个节点的最佳（最短）可能周期？到目前为止，我已经编写了一个基本的替换优化器和一个贪婪的 DFS。我想知道现在开始对我来说最好的方法是什么？

我似乎无法真正理解说问题是 NP-Complete 的真正含义。谁能帮我解决以下问题？

NP完全问题是可以证明不存在在多项式时间内解决它的算法的问题。陈述是真的吗？

我想说这个说法是不正确的，因为任何人都可以真正证明对于任何 NP-Complete 问题都不存在这样的算法吗？通过环顾各种来源，我了解到对于任何 NP-Complete 问题都没有多项式时间算法；但是，无法证明。

任何帮助将不胜感激。谢谢。

我在SO的答案之一中阅读了以下内容：

旅行商问题，正如通常所提出的，是找到连接所有城市的最便宜的路线。这不是决策问题，我们无法直接验证任何提议的解决方案。我们可以将其重述为一个决策问题：给定成本 C，有没有比 C 更便宜的路线？这个问题是 NP 完全的，只需一点点工作，我们就可以像修改后的 NP 完全形式一样简单地求解原始 TSP。因此，TSP 是 NP 难的，因为它至少与 NP 完全问题一样难。

我知道 TSP 是 NP-Complete 但问题是如何 NP-Hard ？我读到NP中但不在P中的问题是NP-Hard。我无法将这件事与 TSP 联系起来。请解释一下。

You are given three things

1) An array of 'n' positive and negative integers. 2) A number 'x'. 3) Operators : '+', '-', '%', '/'

Form an expression with the array such that when you evaluate it, the result becomes 'x'.

For example, consider the array [5,3,-1,6,2,3] and x=2, one possible solution would be

5 / 3 + (-1) + 6 / 2 - 1

Assume the result of 5 / 3 is 1(Always the integer division).

I have one more complex variant of this.

In the complex variant of this problem, assume that BODMASS rule don't apply. So, at any point of time you traversed through elements 'm' and you have the intermediate result 'y'. You can apply any of the operators to the 'y' and a[m + 1].

For example, in the variant 1,

5 + 3 - 2 / 2 = 7 ( 2 / 2 evaluated first, so 5 + 3 - 1)

in the variant 2,

5 + 3 - 2 / 2 = 3 (5 + 3 = 8. The array reduced to 8 - 2 / 2. Now, 8 -2 = 6. And array reduced to 6 / 2 which evaluate to 3).

Algo/Math/DS experts?

Is this a NP hard?