5

動的計画法を使用して、合計が正の整数 K に最も近いが等しくない配列内の正の整数のリストを見つけるにはどうすればよいでしょうか?

私はこれについて考えて少し立ち往生しています。

4

3 に答える 3

6

これの通常の言い回しは、K に最も近いが、K を超えない値を探しているということです。「K 未満」を意味する場合は、K の値が通常よりも 1 大きいことを意味します。本当に「K に等しくない」という意味であれば、基本的にアルゴリズムを 2 回実行します。1 回目は K 未満の最大の合計を見つけ、次に K より大きい最小の合計をもう一度見つけ、絶対値がK との差が最も小さい。

現時点では、K 以下の最大和を本当に意味していると仮定します。これが最も一般的な定式化であり、他の可能性はアルゴリズムにあまり影響を与えないためです。

基本的な考え方はかなり単純ですが、(少なくとも潜在的に) 多くのストレージを使用します。K+1 列と N+1 行 (N = 入力数) のテーブルを作成します。テーブルの最初の行を 0 に初期化します。

次に、テーブルを調べて、実際の最大値まで、可能な最大値ごとに可能な限り最高の値を構築します。行ごとに進み、1 つの入力のみから開始し、次に 2 つの可能な入力、次に 3 つというように進みます。 . 表の各スポットでは、最良の値の可能性は 2 つしかありません: 現在の入力を使用しない以前の最良の値、または現在の入力に最大値の以前の最良の値を加えたものから現在の入力を引いたもの (そして、テーブルの値を順番に計算すると、常にその値が既に存在します)。

また、通常、結果を生成するために実際に使用されたアイテムを追跡したいと考えています。これを行うには、(前の行の最良の値を単にコピーするのではなく) その行の新しい入力を使用してテーブル内のそのスポットの値を計算する場合にのみ、テーブル内の特定のスポットのブール値を true に設定します。最良の結果は右下隅にあるので、そこから始めて、一度に 1 行ずつテーブルを逆方向​​に見ていきます。その列のブール値が true に設定されている行に到達すると、使用された入力が見つかったことがわかります。その項目を出力し、合計からそれを引いて、左の次の列を取得します。この列には、この出力を生成するために使用された次の入力が表示されます。

これは、技術的には C++ で実装されていますが、各ステップをできるだけ明示的にするために、主に C に似たスタイルで記述されています。

#include <iostream>
#include <functional>

#define elements(array) (sizeof(array)/sizeof(array[0]))

int main() {

    // Since we're assuming subscripts from 1..N, I've inserted a dummy value
    // for v[0].
    int v[] = {0, 7, 15, 2, 1};

    // For the moment I'm assuming a maximum <= MAX.
    const int MAX = 17;

    // ... but if you want to specify K as the question implies, where sum<K, 
    // you can get rid of MAX and just specify K directly:
    const int K = MAX + 1;

    const int rows = elements(v);

    int table[rows][K] = {0};
    bool used[rows][K] = {false};

    for (int i=1; i<rows; i++)
        for (int c = 0; c<K; c++) {
            int prev_val = table[i-1][c];
            int new_val;

            // we compute new_val inside the if statement so we won't 
            // accidentally try to use a negative column from the table if v[i]>c
            if (v[i] <= c && (new_val=v[i]+table[i-1][c-v[i]]) > prev_val) {
                table[i][c] = new_val;
                used[i][c] = true;
            }
            else
                table[i][c] = prev_val;
        }

    std::cout << "Result: " << table[rows-1][MAX] << "\n";
    std::cout << "Used items where:\n";
    int column = MAX;
    for (int i=rows; i>-1; i--)
        if (used[i][column]) {
            std::cout << "\tv[" << i << "] = " << v[i] << "\n";
            column -= v[i];
        }

    return 0;
}

これには、通常、最適化することがいくつかあります (読みやすくするために最適化していません)。まず、最適な合計に達した場合は、検索を停止できます。したがって、この場合、 の最終入力を1まったく考慮する前に、実際にループから抜け出すことができます (15と2の望ましい結果が得られるため17)。

第 2 に、テーブル自体では、実際には常に 2 つの行しか使用しません。1 つの現在の行と 1 つの前の行です。その前の行 (メイン テーブル内) は二度と使用されません (つまり、row[n] を計算するには、 、、...からの値は必要ありrow[n-1]ません。ストレージを減らすために、メイン テーブルを 2 つだけにすることができます。これを行うための非常に C に似たトリックは、行番号の最下位ビットのみを使用することです。table -- テーブルをアドレス指定するときではありません。row[n-2]row[n-3]row[0]table[i]table[i-1]table[i&1]table[(i-1)&1]used

于 2012-05-14T07:40:14.680 に答える
3

Python での例を次に示します。

def closestSum(a,k):
  s={0:[]}
  for x in a:
    ns=dict(s)
    for j in s:
      ns[j+x]=s[j]+[x]
    s=ns
  if k in s:
    del s[k]
  return s[min(s,key=lambda i:abs(i-k))]

例：

>>> print closestSum([1,2,5,6],10)
[1, 2, 6]

アイデアは、単純に、配列を調べて前のすべての要素からどのような合計を作成できるか、およびその合計を作成する 1 つの方法を追跡することです。最後に、必要なものに最も近いものを選択するだけです。これは、問題全体をサブ問題に分割し、テーブルを使用してサブ問題の結果を再計算する代わりに記憶するため、動的プログラミング ソリューションです。

于 2012-05-14T05:04:53.743 に答える
1

Racket での Cato のアイデア:

#lang racket
(define (closest-sum xs k)
  (define h (make-hash '([0 . ()])))
  (for* ([x xs] [(s ys) (hash-copy h)])
    (hash-set! h (+ x s) (cons x ys))
    (hash-set! h x (list x)))
  (when (hash-ref h k #f) (hash-remove! h k))
  (cdr (argmin (λ (a) (abs (- k (car a)))) (hash->list h))))

さらに簡潔なプログラムを作成するには、GitHub からterse-hash.rktを取得して次のように記述します。

(define (closest-sum xs k)
  (define h {make '([0 . ()])})
  (for* ([x xs] [(s ys) {copy h}])
    {! h (+ x s) (cons x ys)}
    {! h x (list x)})
  (when {h k #f} {remove! h k})
  (cdr (argmin (λ (a) (abs (- k (car a)))) {->list h})))
于 2012-05-15T14:34:56.973 に答える