No.8090 Knapsack Function

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > ネタ問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 124
作問者 :

SSRS / テスター :

sak

3 ProblemId : 7044 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-03-22 22:08:40

$N$ 個の品物があります。 $i (1 \leq i \leq N)$ 番目の品物の価値は $v_{i}$ 、重さは $w_{i}$ です。
非負整数 $W$ に対し、 $f (W)$ を以下のように定義します。

重さの合計が $W$ と等しくなるように何個かの品物を選ぶとき、選んだ品物の価値の総和の最大値を $f (W)$ とする。ただし、同じ品物を複数回選んでもよい。また、重さの合計が $W$ と等しくなるように品物を選ぶことができないとき、 $f (W) = - 1$ とする。

f

が単調増加であるか、つまり、すべての非負整数

n

について

f (n) < f (n + 1)

が成り立つかどうか判定してください。

 $N$ 
 $v_{1} w_{1}$ 
 $v_{2} w_{2}$ 
 $⋮$ 
 $v_{N} w_{N}$

入力は以下の制約を満たす。

$f$ が単調増加であるならば Yes、そうでないならば No と出力してください。

サンプルはありません。

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