我想在 java 中高效地实现“streaming Knapsack”问题。
问题是我有一个连续输入的整数数据流，例如 -1, 2, 9, 5, 5, 11, 1 -3,...
问题是找到前“k”个元素，其中它们的总和为“n>0”。例如 k=3 和 n=12，则解为:...,2,...,5, 5。
它的高效算法是什么？
最佳答案
保留反向订单PriorityQueue到目前为止，您遇到的 k-1 个最高值整数。每次输入一个新整数时，检查它与那些 k-1 个数字的总和是否大于 n。如果是 - 返回你找到的集合。否则检查此数字是否大于 k-1 数字中的最小值(这就是为什么您需要将优先级队列反向排序的原因)。如果是，则提取最小元素并将新元素插入队列。如果不是简单地转到流中的下一个数字。
关于java - Java 中的流媒体背包，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14443654/