1

Javaで「ストリーミングナップサック」問題を効率的に実装したい。

問題は、整数データのストリーム入力が連続して来ることです。たとえば、-1、2、9、5、5、11、1 -3、...

問題は、それらの合計が「n>0」である最初の「k」要素を見つけることです。たとえば、k=3およびn=12の場合、解は...、2、...、5、5になります。

そのための効率的なアルゴリズムは何ですか？

4

2 に答える 2

1

これまでに出会った最大値の整数の逆順のPriorityQueueを保持します。k-1新しい整数が入力されるたびに、その整数と k-1 個の数値の合計が n より大きいかどうかがチェックされます。そうであれば、見つけたセットを返します。それ以外の場合は、この数値が最小の数値よりも大きいかどうかを確認しk-1ます (そのため、優先キューを逆順にする必要があります)。そうであれば、最小要素を抽出し、新しい要素をキューにプッシュします。そうでない場合は、単にストリーム内の次の番号に移動します。

于 2013-01-21T17:08:18.163 に答える
1

http://programmingpraxis.com/2012/05/15/streaming-knapsack/2/で答えを見つけました :(主に正の整数値用です)

これは動的計画法の問題です。0 から k−1 までの番号が付けられた k 行と 1 から n までの番号が付けられた n 列からなる行列を作成します。行列のすべてのセルは最初は空ですが、行 0 のセルにはそれぞれ null リスト (空のセルと区別できる必要があります) が含まれています。次に、入力ストリームの項目が順番に読み取られます。各アイテム x について、解が見つかり、セル (k-1,n-x) が空でない場合は処理が停止します。解は、セル (k-1,n-x) とアイテム x 内のアイテムのリストです。それ以外の場合、行列内の空でないセル (r,c) ごとに、r+1 の場合

行列はスパースなので、行列の代わりに (r,c) をキーとするハッシュ テーブルを使用します。デモンストレーションでは、正の整数のストリームを提供するために乱数ジェネレータを使用します。

(define (streaming-knapsack k n)
  (define (hash rc) (+ (car rc) (* n (cdr rc))))
  (let ((table (make-hash hash equal? #f 997)))
    (let loop ((x (+ (randint n) 1)))
      (display x) (newline)
      (cond ((table 'lookup (cons (- k 1) (- n x))) =>
              (lambda (xs) (cons x xs)))
      (else (let loop ((xs (table 'enlist)))
              (when (pair? xs)
                (let* ((rcs (car xs)) (r (caar rcs)) (c (cdar rcs))
                       (s (cdr rcs)) (r1 (+ r 1)) (cx (+ c x)))
                  (when (and (< r1 k) (< cx n)
                             (not (table 'lookup (cons r1 cx))))
                    (table 'insert (cons r1 cx) (cons x s))))
                (loop (cdr xs))))
            (when (not (table 'lookup (cons 1 x)))
              (table 'insert (cons 1 x) (list x)))
            (loop (+ (randint n) 1)))))))

外側のループは、入力ストリーム内の項目ごとに 1 回実行されます。入力ストリームをオンザフライで生成しているため、通過する各ストリーム要素が表示されます。cond の最初の句は、ハッシュ テーブルで (r-1, c-x) 項目を探し、存在する場合は結果を返します。そうでない場合、cond の else 句は、ハッシュ テーブル内のすべての項目をループし、すべてのテストに合格した場合は新しいテーブル項目を追加し、存在しない場合は (1 x) テーブル項目を追加し、次の項目にループします。入力ストリーム内の要素。

実際には、2 回発生する式 (+ (randint n) 1) を、入力ストリームから次の項目を取得する関数に置き換え、その関数をパラメーターとして streaming-knapsack に渡す必要があります。

Standard Prelude のハッシュ テーブルと乱数ジェネレーターを使用しました。プログラムはhttp://programmingpraxis.codepad.org/WHdBXcyrで実行できます。

于 2013-01-22T01:47:52.970 に答える