0

以下に示す問題の解決策を見つけるのが困難です。

それぞれが重みを持つ n 個の箱が与えられます (これは、箱 B_i 内の各ボールが重さ C_i を持つことを意味します)。

各ボックスには、{b1,b2,b3...,b_n} (b_i はボックス B_i 内のボールの数) という特定のボールが含まれています。

選択した m 個のボールの重量の合計が所定の数 T 未満になるように、その中から m 個のボールを選択する必要があります。

やり方は何通り？

4

2 に答える 2

4

まず、同様の問題を見てみましょう。

同様の問題は次のとおりです。合計を最大化しようとすると（Tよりもさらに小さくなるように）、 NP困難であるサブセット和問題のバリエーションに直面します。アイテムの数が一定の場合のバリエーションについては、このスレッドで説明しています。固定サブセットサイズの合計サブセット。

問題を調べる別の方法は、2次元のナップサック問題を使用することです。ここで、重み=コスト、および要素数の追加の次元です。この概念はこのスレッドで説明されています：2つのプロパティを持つナップザックの確率を解決するための最速の方法は何ですか

ここで、問題を見てください。Tが小さい/等しい合計を達成するための可能な方法の数を見つけることは、依然としてNP困難です。

それを行うための多項式アルゴリズムがあると仮定し、それをとしますA。

を実行するA(T)とA(T-1)、2つの数値が得られます。場合A(T) > A(T-1)、サブセット和問題の答えはtrue-そうでない場合はですfalse。したがって、この問題の多項式解が与えられると、P=NPであることが証明できます。

于 2012-12-26T11:47:25.753 に答える
1

動的計画法を使用して解決できます。

からまでのボールf[i][j][k]を選択する方法の数を、重みの合計が正確に となるように とします。あなたが得たい答えは です。jB_1B_i kf[n][m][T]

Initially, let f[i][j][k] = 1 for all i,j,k
for i = 1 to n
  for j = 0 to m
    for k = 0 to T
      for x = 0 to min(b_i,j)  # choose x balls from B_i
        y = x * C_i
        if y <= k
          f[i][j][k] = f[i][j][k] * f[i-1][j-x][k-y] * Comb(b_i,x)

Comb(n,k)k要素から要素を選択する方法の数ですn。

時間計算量は O(nm T b) で、b はボックス内のボールの最大数です。

Tbig-O 表記のため、理論的には NP 困難であることに注意してください。ただし、実際には、Tが比較的小さい場合でも、このアルゴリズムは実行可能です。

于 2012-12-26T12:15:28.787 に答える