10

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.

4

5 回答 5

5

如果盒子的数量没有限制，那么通过从3 分区减少（设置 n/3 个盒子并使用值 = 权重使所有事物变成彩虹色），这个问题是强 NP 难的。

如果盒子的数量是恒定的，那么就有一个通过动态规划的伪多项式时间算法，其中每个 DP 状态由每个盒子的填充程度组成。

于 2012-04-12T19:48:56.187 回答
5

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

如果具有相同颜色组合的球必须具有相同的重量和值，请考虑当您有红色/蓝色、红色/绿色等球且只有一个红色框的情况。

于 2012-04-12T17:10:27.150 回答
3

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

也就是说，它不仅仅是类似于背包问题：如果有一个碗，所有的球都有那个碗的颜色，碗里的最大球数是球的总数，那么问题就是背包问题.

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

于 2012-04-12T17:16:14.207 回答
3

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

于 2012-04-12T17:11:10.397 回答
0

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

于 2012-04-12T17:13:07.127 回答