No.2167 Fibonacci Knapsack
タグ : / 解いたユーザー数 24
作問者 :
hamamu
Problem Statement
Let the Fibonacci numbers $F_n$ be the sequence defined by the following recurrence. $$F_n = \begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ F_{n - 2} + F_{n - 1} & n \ge 3 \end{cases}$$
There are $N$ items, numbered $1, 2, \ldots, N$. For each $i = 1, 2, \ldots, N$, item $i$ has weight $w_i$ and value $F_{i}$.
Magurofly is going to pack some of these items into a suitcase and carry them. However, the total weight packed into the suitcase must be at most $W$.
Find the maximum possible total value of the items packed into the suitcase (if there is no item that can be packed into the suitcase, the answer is $0$). It can be proved that, under the constraints of this problem, the total value does not exceed $10^{18}$.
Solve this for $T$ test cases.
Input
The input is given in the following format.$T$
$case_1$
$case_2$
$\vdots$
$case_{T}$
Each test case is given in the following format.
$N$ $W$ $w_1$ $w_2$ $\dots$ $w_N$
- $1 \le T \le 100$
- $1 \le N \le 75$
- $1 \le W \le 10^{18}$
- $1 \le w_i \le 10^{16}$
- All input values are integers.
Output
Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.
Sample
Sample 1
Input
1 5 7 1 2 3 4 5
Output
10
Choosing items $2,\ 5$ makes the total value $F_2+F_5=2+8=10$. There is no way to make the total value any larger, so the answer is $10$.
Sample 2
Input
1 5 7 8 9 10 11 12
Output
0
The weight of an item may exceed $W$. In this case, not even $1$ item can be packed into the suitcase, so the answer is $0$.
Sample 3
Input
2 11 50 1 3 3 3 12 129 13 34 68 30 24 20 6023 286 1304 1882 1144 6 1154 642 136 1076 1638 968 1266 448 374 288 1298 1708 1344 580 1088
Output
176 26492
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。