No.3401 Large Knapsack Problem
Problem Statement
There are $N$ types of items. There are $10^{10^{100}}$ copies of each item, and the $i\ (1 \leq i \leq N)$-th item has value
$v_{i}$ and weight $w_{i}$.
You have a knapsack with a weight capacity of $W$. When you put items into the knapsack so that the total weight of the chosen items does not exceed $W$, what is the maximum possible total value?
Input
$N$ $W$
$v_{1}$ $w_{1}$
$v_{2}$ $w_{2}$
$\vdots$
$v_{N}$ $w_{N}$
Constraints
- $1 \leq N \leq 20$
- $1 \leq W \leq 10^{9}$
- $1 \leq v_{i} \leq 1000$
- $1 \leq w_{i} \leq 1000$
Output
Output the maximum total value.
Sample
Sample 1
Input
3 7 2 3 3 4 4 5
Output
5
The optimal solution is to choose $1$ copy of the $1$-st item and $1$ copy of the $2$-nd item.
Sample 2
Input
1 1000000000 1000 1
Output
1000000000000
Note that you can buy a large number of copies of $1$ item, and that the answer may not fit in a 32-bit integer type.
Sample 3
Input
4 191 9 9 4 8 12 22 1000 400
Output
189
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。