0

knapsack問題は(またはそのタイプで、値がなく、正の重みのみ)よりも単純です。この問題は、数が他の数の組み合わせになり得るかどうかをチェックすることから成ります。関数はtrueまたはを返す必要がありfalseます。

例えば、

112 と、{ 17, 100, 101 }を返す必要があるリストfalse、469同じリストを返す必要がある、返す必要があるtrue、返す必要がある、など...35false119true

編集：ナップザックよりもサブセットサムの問題の方が正確です。

4

4 に答える 4

3

これはサブセット合計問題の特殊なケースであり、セットに 1 つの負の数のみが含まれます (つまり、112 と { 17, 100, 101 } を { -112, 17, 100, 101 } として表現します)。ウィキペディアのページhttp://en.wikipedia.org/wiki/Subset_sum_problemにいくつかのアルゴリズムがあります。

于 2010-01-28T08:08:25.050 に答える
2

役立つ観察は、リストが {a, b, c...} で、テストしたい数が x の場合、x または xa のいずれかができる場合にのみ、x をサブリストの合計として書くことができるということです。サブリスト {b, c, ...} の合計として記述されます。これにより、問題を解決するための非常に単純な再帰アルゴリズムを作成できます。

編集：以下のコメントを考慮したコードを次に示します。テストされていないため、おそらくバグがあります。必ずしも最速ではありません。ただし、小さなデータセットの場合は、仕事をうまく終わらせることができます。

bool is_subset_sum(int x, std::list::const_iterator start, std::list::const_iterator end)
{
  // for a 1-element list {a} we just need to test a|x
  if (start == end) return (x % *start == 0); 

  // if x is small enough  we don't need to bother testing x - a
  if (x<a) return is_subset_sum (x, start+1, end);

  // the default case. Note that the shortcut properties of || means the process ends as soon as we get a positive.
  return (is_subset_sum (x, start+1, end) || is_subset_sum (x-a, start, end));
}
于 2010-01-28T08:04:49.553 に答える
2

クエリされた数が大きくなるにつれて、肯定的な結果が濃くなることに注意してください。たとえば、100^2 より大きいすべての数値は、{ 17, 100, 101 } で生成できます。したがって、最適なアルゴリズムは、クエリされた数がセットのメンバーよりもはるかに大きいかどうかによって異なります。場の理論を調べるかもしれません。

少なくとも、セットの最大公約数がクエリに含まれていない場合、結果は常に false であり、無視できる時間で確認できることがわかっています。

于 2010-01-28T08:30:21.507 に答える
1

到達する数が大きすぎない場合は、範囲 [1,N] に含まれるセットから到達可能なすべての数を生成できる可能性があります。

N問題: list 内の要素を使用してリーチしますL。ここで、は十分に小さいため、サイズ要素のサイズNのベクトルを気にする必要はありません。N

アルゴリズム：

  • Vサイズのベクトルを生成するN
  • lリスト内の各要素に対してL
    • 到達可能な要素ごとvにV
      • v + n*lV のすべての要素を到達可能としてマークする
于 2010-01-28T08:42:05.330 に答える