Sophisticated knapsack problem

Revision en2, by egor.okhterov, 2016-12-17 12:52:34

There are n boxes. Boxes contain marbles.
Box number 1 contains 1 marble.
Box number 2 contains 2 marbles.
...
Box number n contains n marbles.

We have to choose exactly b boxes out of n original boxes, so that we would have exactly t marbles in total.

For example, if we have a set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 4 boxes to get the total target value t = 13, then we should output 1 3 4 5.

But if we have the same set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 3 boxes with the same total value of t = 13, then we have to print Impossible.


I have a simple bruteforce solution, which is working, but for too long. And I have a dynamic programming solution, which is not correct:

Bruteforce

My dp solution is not correct, because it remembers only one configuration. For example, to get target value t = 5, we can choose (1, 4) or we can choose (2, 3). My code will remember only one of those 2 choices.

The task becomes even more complicated when we are given the following constraints:
1 ≤ n ≤ 1018
1 ≤ t ≤ 106
1 ≤ b ≤ n

Tags dynamic programming, knapsack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian egor.okhterov 2016-12-17 14:07:11 1071
en3 English egor.okhterov 2016-12-17 12:57:14 40 Tiny change: 'There are ' -
en2 English egor.okhterov 2016-12-17 12:52:34 3 Tiny change: ' when we a given the' -> ' when we are given the'
en1 English egor.okhterov 2016-12-17 12:51:00 1704 Initial revision for English translation (published)
ru1 Russian egor.okhterov 2016-12-16 15:16:48 676 Первая редакция (сохранено в черновиках)