103735: [Atcoder]ABC373 F - Knapsack with Diminishing Values
Description
Score : $550$ points
Problem Statement
There are $N$ types of items. The $i$-th type of item has a weight of $w_i$ and a value of $v_i$. Each type has $10^{10}$ items available.
Takahashi is going to choose some items and put them into a bag with capacity $W$. He wants to maximize the value of the selected items while avoiding choosing too many items of the same type. Hence, he defines the happiness of choosing $k_i$ items of type $i$ as $k_i v_i - k_i^2$. He wants to choose items to maximize the total happiness over all types while keeping the total weight at most $W$. Calculate the maximum total happiness he can achieve.
Constraints
- $1 \leq N \leq 3000$
- $1 \leq W \leq 3000$
- $1 \leq w_i \leq W$
- $1 \leq v_i \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ $\vdots$ $w_N$ $v_N$
Output
Print the answer.
Sample Input 1
2 10 3 4 3 2
Sample Output 1
5
By choosing $2$ items of type $1$ and $1$ item of type $2$, the total happiness can be $5$, which is optimal.
Here, the happiness for type $1$ is $2 \times 4 - 2^2 = 4$, and the happiness for type $2$ is $1 \times 2 - 1^2 = 1$.
The total weight is $9$, which is within the capacity $10$.
Sample Input 2
3 6 1 4 2 3 2 7
Sample Output 2
14
Sample Input 3
1 10 1 7
Sample Output 3
12
Output
问题陈述
有$N$种物品。第$i$种物品的重量为$w_i$,价值为$v_i$。每种物品都有$10^{10}$个可用。
高桥打算选择一些物品并将它们放入容量为$W$的背包中。他希望在选择的物品中最大化价值,同时避免选择太多同一类型的物品。因此,他定义选择$k_i$个第$i$种物品的幸福感为$k_i v_i - k_i^2$。他想要选择物品,以在所有类型上最大化总幸福感,同时保持总重量最多为$W$。计算他可以达到的最大总幸福感。
约束条件
- $1 \leq N \leq 3000$
- $1 \leq W \leq 3000$
- $1 \leq w_i \leq W$
- $1 \leq v_i \leq 10^9$
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出:
$N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ $\vdots$ $w_N$ $v_N$
输出
打印答案。
样本输入 1
2 10 3 4 3 2
样本输出 1
5
通过选择2个第1种物品和1个第2种物品,总幸福感可以达到5,这是最优的。
这里,第1种物品的幸福感是$2 \times 4 - 2^2 = 4$,第2种物品的幸福感是$1 \times 2 - 1^2 = 1$。
总重量是9,这在容量10的范围内。
样本输入 2
3 6 1 4 2 3 2 7
样本输出 2
14
样本输入 3
1 10 1 7
样本输出 3
12