Doka Eating

2 secs 1024 MB

基本方針

$100$ グラム $1$ 円のハンバーガーが常に存在することに着目します。

このハンバーガーの存在によって、 $1000$ 円以上のハンバーガーを注文する意味が完全になくなります。（重さが $\text{max}W = 10^5$ グラムだとしても $100$ グラム $1$ 円のハンバーガーの方がお得なので）

同じ値段のハンバーガーについては、重さが一番大きいものだけに選択肢を絞ることができます。

以上の考察を踏まえ、適切にハンバーガーを除外することで以下の制約の個数制限なしナップザック問題に帰着させることができます。

ここからの解説は以下の記事を参考にすると良いでしょう。