No.2026 Yet Another Knapsack Problem
タグ : / 解いたユーザー数 21
作問者 :
suisen
/ テスター :
chineristAC
Problem Statement
There are $N$ types of items. For each $i\ (1\leq i \leq N)$, there are $c _ i$ items of type $i$, each with weight $i$ and value $v _ i$.
There are $\displaystyle \sum _ {i = 1} ^ N c _ i$ items in total, and suisen is going to choose some of them so that the total weight is at most $N$.
For every $k=1,\ldots,N$, find the maximum total value of the chosen items when suisen chooses exactly $k$ items. Under the constraints of this problem, it can be proved that for every $k=1,\ldots,N$, suisen can choose exactly $k$ items so that the total weight is at most $N$.
Input
$N$ $c_1\ v_1$ $c_2\ v_2$ $\vdots$ $c_N\ v_N$
- All input values are integers.
- $1\leq N \leq 2500$
- $1\leq c _ i \leq N$
- In particular, $c _ 1 = N$ holds.
- $-10 ^ 9\leq v _ i \leq 10 ^ 9$
Output
Print $N$ lines. On the $k\ (1\leq k\leq N)$-th line, print the maximum total value of the chosen items when choosing exactly $k$ items so that the total weight is at most $N$.
Sample
Sample 1
Input
6 6 -10 1 6 4 3 3 -1 5 4 2 0
Output
6 9 -1 -24 -34 -60
The input represents the following.
- There are $6$ items of weight $1$, each with value $-10$.
- There are $1$ items of weight $2$, each with value $6$.
- There are $4$ items of weight $3$, each with value $3$.
- There are $3$ items of weight $4$, each with value $-1$.
- There are $5$ items of weight $5$, each with value $4$.
- There are $2$ items of weight $6$, each with value $0$.
The output is explained below.
When choosing $1$ item so that the total weight is at most $6$, the total value is maximized by choosing $1$ item of weight $2$, and that total is $6$.
When choosing $2$ items, the total value is maximized by choosing $1$ item each of weight $2$ and weight $3$, and that total is $9$. Note that there is only $1$ item of weight $2$, so you cannot choose $2$ of them. Also, choosing $1$ item each of weight $2$ and weight $5$ satisfies the condition on the number of items, but the total weight would be $7$, which exceeds $6$, so this is not allowed.
When choosing $3$ items, it is optimal to choose $1$ item each of weights $1,2,3$, and the total value is $-1$. Note that the total value can be negative.
It can be proved that the maximum total values when choosing $4,5,6$ items are $-24,-34,-60$, respectively.
Sample 2
Input
10 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000 10 1000000000
Output
1000000000 2000000000 3000000000 4000000000 5000000000 6000000000 7000000000 8000000000 9000000000 10000000000
Beware of overflow.
Sample 3
Input
6 6 1 1 2 1 4 1 8 1 16 1 32
Output
32 17 10 7 6 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。