NP Knapsack problem#4178
One of the classic NP - complete problems is the so-called Knapsack problem. It is formulated as follows.
items are given, each of which is characterized by weight w_i and usefulness p_i. It is necessary to choose a certain set of these items so that the total weight of this set does not exceed , and the total usefulness is maximum.
First line contains positive integers (1 \leq n \leq 20) and (1 \leq w \leq 10^9). Next lines with two integers are given: the weight of the -th item w_i and its usefulness p_i (1 \leq w_i, p_i \leq 10^9).
On the first line print the number of selected items and their total usefulness. On the second line print their numbers in ascending order (items are numbered starting from one in the order in which they are given at the input).
If there exists several outputs, choose the one with the smallest number of items. If after that the answer is still ambiguous, choose the set where the first item has the lowest possible number, from all such options, choose the one in which the second item has the lowest possible number, etc.
Örnek 1