10

指定: 整数値の配列 K,M

質問: 与えられた配列のすべての K 個の要素サブセットから、合計が値 M 未満になるように取得できる最大合計を見つけますか?

この問題に利用できる非動的プログラミング ソリューションはありますか? または、dp[i][j][k] のみの場合は、このタイプの問題しか解決できません! アルゴリズムを教えてください。

4

3 に答える 3

8

多くの人が、動的プログラミングを使用する数年前からの以下の回答が、配列の要素が「サブセット」に複数回出現することを可能にするソリューションを誤ってエンコードしていると正しくコメントしています。幸いなことに、DP ベースのアプローチにはまだ希望があります。

入力配列の最初の要素のサイズのサブセットがdp[i][j][k]存在する場合、合計するとkij

私たちのベースケースはdp[0][0][0] = true

ここで、最初の要素のサイズkサブセットが を使用するか、または使用しないかのいずれかで、繰り返しia[i + 1]

dp[i + 1][j][k] = dp[i][j - a[i + 1]][k - 1] OR dp[i][j][k]

すべてをまとめる：

given A[1...N]
initialize dp[0...N][0...M][0...K] to false
dp[0][0][0] = true
for i = 0 to N - 1:
    for j = 0 to M:
        for k = 0 to K:
            if dp[i][j][k]:
                dp[i + 1][j][k] = true
            if j >= A[i] and k >= 1 and dp[i][j - A[i + 1]][k - 1]:
                dp[i + 1][j][k] = true
max_sum = 0
for j = 0 to M:
    if dp[N][j][K]:
        max_sum = j
return max_sum

O(NMK)時間と空間の複雑さを与えます。

一歩戻って、ここで暗黙のうちに 1 つの仮定を行いましたが、それA[1...i]はすべて非負であるということです。負の数の場合、2 番目の次元の初期化は0...M正しくありません。合計が を超えるサイズ サブセットと、全体の合計が を超えないような十分に負の要素が 1つあるKサイズ サブセットで構成されるサイズ サブセットを考えてみましょう。同様に、サイズのサブセットを合計すると、非常に負の数になり、合計の要素が十分に正になる可能性があります。アルゴリズムが両方のケースで引き続き機能するためには、2 番目の次元を からのすべての正の要素の合計の差まで増やす必要があります。K - 1MA[]MK - 1A[]MMA[]およびすべての負の要素の合計 ( 内のすべての要素の絶対値の合計A[])。

非動的計画法の解決策が存在するかどうかについては、単純な指数時間のブルート フォースの解決策と、指数の定数係数を最適化するバリエーションが確かに存在します。

それ以上？あなたの問題はサブセットサムと密接に関連しており、有名なNP完全問題の文献はかなり広範です。そして、一般的な原則として、アルゴリズムはあらゆる形状とサイズで実現できます-ランダム化、近似などを行うことを想像することは不可能ではありません(エラーパラメーターが十分に小さくなるように選択するだけです!)他のNP完全問題への単純な古い還元(問題を巨大なブール回路に変換し、SAT ソルバーを実行します)。はい、これらは異なるアルゴリズムです。それらは動的計画法ソリューションよりも高速ですか? それらのいくつか、おそらく。それらは、アルゴリズム資料の標準的な導入を超えたトレーニングがなくても、理解したり実装したりするのが簡単ですか? おそらくそうではありません。

これはナップザックまたはサブセット問題の変形であり、時間の観点から (入力サイズが大きくなるにつれて指数関数的に増加するスペース要件を犠牲にして)、動的計画法がこの問題を正しく解決する最も効率的な方法です。部分和問題のこのバリアントはより簡単に解決できますか? を参照してください。あなたと同様の質問について。

ただし、問題はまったく同じではないため、とにかく説明を提供します。dp[i][j]= に合計するtrue長さのサブセットがある場合、ない場合は=とします。アイデアは、可能なすべての長さのすべての可能なサブセットの合計をエンコードすることです。次に、 であるような最大のものを簡単に見つけることができます。サイズ 0 の 1 つを選択することで、合計が 0 になるサブセットを常に作成できるため、基本ケースです。ijfalsedp[][]j <= Mdp[K][j]truedp[0][0] = true

再発もかなり簡単です。配列dp[][]の最初の値を使用して の値を計算したとします。配列の最初の値のnすべての可能なサブセットを見つけるには、単純に_th の値を取り、それを前に見たすべてのサブセットに追加します。より具体的には、次のコードがあります。n+1n+1

initialize dp[0..K][0..M] to false
dp[0][0] = true
for i = 0 to N:
    for s = 0 to K - 1:
        for j = M to 0:
            if dp[s][j] && A[i] + j < M:
                dp[s + 1][j + A[i]] = true
for j = M to 0:
    if dp[K][j]:
        print j
        break

于 2013-08-06T13:57:57.707 に答える
1

要素の合計が最大である要素のサブセットを探していますKが、 未満ですM。

[X, Y]次のように、サブセット内の最大の要素に境界を設定できます。

最初に (N) 個の整数values[0] ... values[N-1]を、要素values[0]が最小になるように並べ替えます。

下限Xは、最大の整数です。

values[X] + values[X-1] + .... + values[X-(K-1)] < M.

(XがN-1の場合、答えが見つかりました。)

上限Yは、それより小さい最大の整数Nです。

values[0] + values[1] + ... + values[K-2] + values[Y] < M.

この観察により、最高項 の各値に対して 2 番目に高い項を制限できるようになりましたZ。ここで、

X <= Z <= Y.

問題の形式がまったく同じなので、まったく同じ方法を使用できます。削減された問題は、要素の合計が最大であるが 未満であるK-1から取得された要素のサブセットを見つけることです。values[0] ... values[Z-1]M - values[Z]

同じ方法でその値をバインドしたら、2 つの最大値のペアごとに 3 番目に大きい値に境界を設定できます。等々。

これにより、検索するツリー構造が得られます。うまくいけば、N が K を選択するよりもはるかに少ない組み合わせで検索できます。

于 2013-08-05T22:36:24.103 に答える
0

これがナップザック問題の特殊なケースであるという Felix の意見は正しい。彼の動的計画法アルゴリズムは、O (K*M) サイズとO (K*K*M) 時間かかります。彼の変数 N の使用は、実際には K であるべきだと思います。

ナップザック問題を扱った本が 2 冊あります。Kellerer、Pferschy、および Pisinger [2004 年、Springer-Verlag、ISBN 3-540-40286-1] による最新のものでは、76 ページの図 4.2 で、O (K+M) 空間とOを使用する改良された動的計画法アルゴリズムが示されています。 (KM) 時間。これは、Felix によって提供された動的計画法アルゴリズムと比較して大幅に削減されます。c-bar := c-bar - w_(r(c-bar)) であるはずのアルゴリズムの本の最後の行にタイプミスがあることに注意してください。

私のC#実装は以下です。十分にテストしたとは言えませんが、これに関するフィードバックを歓迎します。BitArray本のアルゴリズムで与えられたセットの概念を実装していました。私のコードでcは、 は容量 (元の投稿では M と呼ばれていました) であり、w代わりにA重みを保持する配列として使用しました。

その使用例は次のとおりです。

int[] optimal_indexes_for_ssp = new SubsetSumProblem(12, new List<int> { 1, 3, 5, 6 }).SolveSubsetSumProblem();

ここで、配列optimal_indexes_for_sspには要素 1、5、6 に対応する [0,2,3] が含まれます。

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

public class SubsetSumProblem
{
    private int[] w;
    private int c;

    public SubsetSumProblem(int c, IEnumerable<int> w)
    {
      if (c < 0) throw new ArgumentOutOfRangeException("Capacity for subset sum problem must be at least 0, but input was: " + c.ToString());
      int n = w.Count();
      this.w = new int[n];
      this.c = c;
      IEnumerator<int> pwi = w.GetEnumerator();
      pwi.MoveNext();
      for (int i = 0; i < n; i++, pwi.MoveNext())
        this.w[i] = pwi.Current;
    }

    public int[] SolveSubsetSumProblem()
    {
      int n = w.Length;
      int[] r = new int[c+1];
      BitArray R = new BitArray(c+1);
      R[0] = true;
      BitArray Rp = new BitArray(c+1);
      for (int d =0; d<=c ; d++) r[d] = 0;
      for (int j = 0; j < n; j++)
      {
        Rp.SetAll(false);
        for (int k = 0; k <= c; k++)
          if (R[k] && k + w[j] <= c) Rp[k + w[j]] = true;
        for (int k = w[j]; k <= c; k++) // since Rp[k]=false for k<w[j]
          if (Rp[k])
          {
            if (!R[k]) r[k] = j;
            R[k] = true;
          }
      }
      int capacity_used= 0;
      for(int d=c; d>=0; d--)
        if (R[d])
        {
          capacity_used = d;
          break;
        }
      List<int> result = new List<int>();
      while (capacity_used > 0)
      {
        result.Add(r[capacity_used]);
        capacity_used -= w[r[capacity_used]];
      } ;
      if (capacity_used < 0) throw new Exception("Subset sum program has an internal logic error");
      return result.ToArray();
    }
}
于 2013-08-30T14:26:58.490 に答える