10

私はこの問題に対して合理的なアルゴリズムを考え出そうとしています:

ボールがたくさんあるとしましょう。各ボールには少なくとも 1 つの色がありますが、多色にすることもできます。各ボールには、それに関連付けられた重量と値があります。ワンカラーのボックスもたくさんあります。各ボックスには、保持できるボールの最大数があります。目標は、合計の重み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)

注: 緑/赤/青のボールは赤/青のボールよりも価値がありましたが、その重さから限界を超えていたでしょう。

編集：

1 つの明確なポイント: 同じ色の組み合わせのボールは、必ずしも同じ重量と値を持つとは限りません。たとえば、値が 3 で重みが 1 の赤いボールと、値が 2 で重みが 5 の別の赤いボールを作成できます。

編集2：

動的計画法アルゴリズムを考え出すのに役立つ場合は、整数の重みと値を想定できます。

4

5 に答える 5

5

これは、少なくともナップザック問題と同じくらい複雑です。すべてのボールが赤で、赤いボックスが 1 つしかない場合を考えてみてください。

同じ色の組み合わせを持つボールが同じ重みと値を持つ必要がある場合、赤/青、赤/緑などのボールと赤のボックスが 1 つしかない場合を考えてみましょう。

于 2012-04-12T17:10:27.150 に答える
5

ボックスの数に制限がない場合、この問題は3 パーティションからの削減によって強く NP 困難になります (n/3 個のボックスを設定し、値 = 重みですべてのものを虹色にします)。

ボックスの数が一定の場合、動的計画法による疑似多項式時間アルゴリズムがあり、各 DP 状態は各ボックスがどれだけいっぱいかで構成されます。

于 2012-04-12T19:48:56.187 に答える
3

ナップザックからの還元は以下の通りです。ナップザック インスタンスを指定して、ボールとビンの問題のインスタンスを作成します。ナップザック インスタンスの各アイテムに対して、アイテムと同じ重さと値を持つボールがあります。次に、ナップザックを表すボックスがあります。ボールと箱はすべて青色です。箱の容量はナップザック問題で与えられた限界です。問題の解決策を考えると、合計重量がナップザックの制限以下で、合計値が最大になる一連のボールが箱に入っています。

于 2012-04-12T17:11:10.397 に答える
3

この問題は、ナップザック問題を包含しているため、NP 完全です。

つまり、ナップザック問題に似ているだけではありません。ボウルが 1 つあり、すべてのボールがそのボウルの色を持ち、ボウル内のボールの最大数がボールの総数である場合、問題はまさにナップザック問題です。 .

アルゴリズムがこの問題を多項式時間で解くことができれば、あらゆるナップザックの問題を多項式時間で解くことができます。しかし、ナップザック問題は NP 完全なので、この問題も NP 完全です。

于 2012-04-12T17:16:14.207 に答える