No.3401 Large Knapsack Problem
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 :
sclara
/ テスター :
kencho
タグ : / 解いたユーザー数 35
作問者 :
sclara
/ テスター :
kencho
問題文最終更新日: 2025-12-06 23:29:38
コンテストの他の問題:
問題文
$N$ 種類の品物があります。各品物はそれぞれ $10^{10^{100}}$ 個あり、 $i\ (1 \leq i \leq N)$ 番目の品物の価値は
$v_{i}$ で、重さは $w_{i}$ です。
あなたは、許容重量が $W$ のナップサックを持っています。 選んだ品物の重さの合計が $W$ を超えないようにナップサックに品物を入れたとき、価値の合計の最大値はいくつになりますか。
入力
$N$ $W$
$v_{1}$ $w_{1}$
$v_{2}$ $w_{2}$
$\vdots$
$v_{N}$ $w_{N}$
制約
- $1 \leq N \leq 20$
- $1 \leq W \leq 10^{9}$
- $1 \leq v_{i} \leq 1000$
- $1 \leq w_{i} \leq 1000$
出力
価値の合計の最大値を出力してください。
サンプル
サンプル1
入力
3 7 2 3 3 4 4 5
出力
5
$1$ 番目の品物を $1$ つと、 $2$ 番目の品物を $1$ つ選ぶのが最適解です。
サンプル2
入力
1 1000000000 1000 1
出力
1000000000000
$1$ つの品物を大量に買うことができることや、答えが32bit整数型に収まらない可能性があることに注意してください。
サンプル3
入力
4 191 9 9 4 8 12 22 1000 400
出力
189
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。