java - Java中的流式背包

Question

我想在java中有效地实现“流式背包”问题。

问题是我有一个连续输入的整数数据流，例如 -1、2、9、5、5、11、1 -3、...

问题是找到它们的总和为“n>0”的前“k”个元素。例如 k=3 和 n=12，则解为：...,2,...,5, 5。

它的有效算法是什么？

Answer 1

保留到目前为止您遇到的最高值整数的反向排序PriorityQueue 。k-1每次输入一个新整数时，检查它和那些 k-1 个数字的总和是否大于 n。如果是 - 返回您找到的集合。否则检查这个数字是否大于最小的k-1数字（这就是为什么你需要对优先级队列进行反向排序）。如果是，则提取最小元素并将新元素推入队列。如果不是简单地转到流中的下一个数字。

Answer 2

我在http://programmingpraxis.com/2012/05/15/streaming-knapsack/2/中找到了答案 ：（主要用于正整数值）

这是动态规划的问题。构造一个矩阵，其中 k 行编号为 0 到 k-1，n 列编号为 1 到 n。矩阵的所有单元格最初都是空的，除了第 0 行中的每个单元格都包含空列表（必须与空单元格区分开来）。然后按顺序读取输入流的各项。对于每个项目 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)))))))

外循环对输入流中的每个项目运行一次；因为我们正在动态生成输入流，它会在每个流元素通过时显示它。cond 的第一个子句在哈希表中查找 (r-1, c-x) 项，如果存在则返回结果。如果不是，则 cond 的 else 子句循环遍历哈希表中的所有项目，如果所有测试都通过，则添加一个新表项，如果不存在则添加一个 (1 x) 表项，然后循环到下一个输入流中的元素。

在实践中，您应该将出现两次的表达式 (+ (randint n) 1) 替换为从输入流中获取下一项的函数，并将该函数作为参数传递给 streaming-knapsack。

我们使用了来自 Standard Prelude 的哈希表和随机数生成器。您可以在http://programmingpraxis.codepad.org/WHdBXcyr上运行该程序。