Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to implement efficiently "streaming Knapsack" problem in java.

The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,...

The question is to find the first "k" elements in which their sum is "n>0". for example k=3 and n=12, then the solution is: ...,2,...,5, 5.

I found an answer in http://programmingpraxis.com/2012/05/15/streaming-knapsack/2/ as: (It is mainly for positive Integer Values)

But looking for simpler one! Any Ideas?

share|cite|improve this question
2  
What do you mean by simpler ones? Faster ones? Ones requiring less memory? Ones easier to program? – Yuval Filmus Jan 25 '13 at 21:13
    
faster and simpler to code – Reza Jan 25 '13 at 22:20
2  
I'm not sure that there is any faster simple solution (or any faster solution at all), and I don't think that this dynamic programming solution is that hard to code, even in Java. – Yuval Filmus Jan 25 '13 at 22:51
    
You meantion you get a "stream" of data. Does that impose any restrictions on the algorithm? For example, does it have unlimited memory? – Raphael Jan 26 '13 at 17:51
    
yes, it should be memory efficient. – Reza Jan 26 '13 at 18:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.