Sophisticated knapsack problem

Revision ru1, by egor.okhterov, 2016-12-16 15:16:48

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.


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 Первая редакция (сохранено в черновиках)