問題一覧 > 通常問題

No.2167 Fibonacci Knapsack

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : chineristACchineristAC / テスター : hamamuhamamu
2 ProblemId : 8871 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-18 21:48:23

問題文

フィボナッチ数 $F_n$ を、次の漸化式で定義される数列とします。 $$F_n = \begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ F_{n - 2} + F_{n - 1} & n \ge 3 \end{cases}$$

$N$ 個の品物があります。品物には $1, 2, \ldots, N$ と番号が振られています。各 $i = 1, 2, \ldots, N$ について、品物 $i$ の重さは $w_i$ で、価値は $F_{i}$ です。

まぐふらい君は、これらの品物をスーツケースに詰めて運ぼうとしています。ただし、スーツケースに詰める重さの総和は $W$ 以下である必要があります。

スーツケースに詰める品物の、価値の総和の最大値を求めてください(ただし、スーツケースに詰められる品物が存在しない場合は $0$ としてください)。なお、この問題の制約下で、価値の総和は $10^{18}$ を超えないことが証明できます。

$T$ 個のテストケースについて求めてください。

入力

入力は以下の形式で与えられます。
$T$
$case_1$
$case_2$
$\vdots$
$case_{T}$
各テストケースは以下の形式で与えられます。
$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}$
  • 与えられる入力はすべて整数

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースの答えを出力して下さい。

サンプル

サンプル1
入力
1
5 7
1 2 3 4 5
出力
10

$2,\ 5$ 番目の品物を選ぶと価値の総和を $F_2+F_5=2+8=10$ にできます。価値の総和をこれ以上大きくする方法はないので答えは $10$ になります。

サンプル2
入力
1
5 7
8 9 10 11 12
出力
0

品物の重さは $W$ を超えることがあります。このケースでは品物は $1$ つもスーツケースに詰めることができないので答えは $0$ です。

サンプル3
入力
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
出力
176
26492

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。