No.2869 yuusaan's Knapsacks
タグ : / 解いたユーザー数 47
作問者 :
寝癖
👑 Note
The time limit is strict, so we recommend using a fast language.
Story
Once again, you have been taken to a parallel world by Yuusaan.
"All right, I'm going to decide the importance of the things I find here again, so make sure you can compute the maximum total importance within what fits in the knapsacks.
This time I don't need any objects with negative mass... but I want to pack lots of everything else, so I brought many knapsacks.
Oh, that's right. While you're at it, write the code so that it also tells me how to pack the things."
Problem Statement
There are $N$ knapsacks and $M$ items. The knapsacks are numbered from $1$ to $N$, and the items are numbered from $1$ to $M$.
Here, for each pair of integers $i,j(1\leq i \leq N,1\leq j \leq M)$, knapsack $i$ has durability $e_i$, and item $j$ has value $v_j$ and weight $w_j$.
Yuusaan puts $0$ or more items into each knapsack. For every knapsack, the total weight of the items put into it must not exceed its durability.
Also, a single item cannot be put into more than one knapsack.
Among the ways of packing items that satisfy the above conditions, find the maximum possible total value of the items put into the knapsacks.
Also, show one way of packing items that achieves this maximum total value. (See the "Output" section for the specific output format.)
(Note that in this problem, $e_i$ is not a symbol representing Napier's constant.)
Input
$N\ M$ $e_1\ e_2 \ e_3 \dots e_N$ $v_1\ w_1$ $v_2\ w_2$ $\vdots$ $v_M\ w_M$
Constraints
- $1\leq N \leq M$
- $1\leq M \leq $ $16$
- $1\leq e_i \leq 10^9$
- $1\leq w_i\leq 10^9$
- $1\leq v_i \leq 10^7$
- All inputs are integers.
Output
Output $N+1$ lines.
On line $1$, output the maximum possible total value of the items put into the knapsacks.
On line $2$ onward, output one way of packing items that maximizes the total value of the items.
More specifically, for that way of packing, on line $i+1$, output the number of items put into knapsack $i$ followed by the numbers of all the items put into it, in this order, separated by spaces.
If there are multiple solutions satisfying the conditions, any of them will be accepted.
Print a newline at the end.
Sample
Sample 1
Input
3 5 5 2 3 2 2 3 2 5 3 3 3 3 4
Sample Output
13 2 1 3 1 2 1 4
If items $1,3$ are put into knapsack $1$, item $2$ into knapsack $2$, and item $4$ into knapsack $3$, the total value is $13$, which is the maximum.
Other ways of packing, such as putting items $2,4$ into knapsack $1$, item $1$ into knapsack $2$, and item $3$ into knapsack $3$, are also accepted.
Sample 2
Input
5 5 10 15 20 25 30 100 50 100 50 100 50 100 50 100 50
Sample Output
0 0 0 0 0 0
All the items are too heavy, so none of them can be put into a knapsack.
Sample 3
Input
5 6 4 7 1 2 1 23 2 14 5 72 7 21 2 35 3 12 1
Sample Output
142 2 5 6 1 3 0 1 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。