競プロ日和

競技プログラミングを楽しむ

AtCoder Educational DP Contest / DP まとめコンテスト E - Knapsack 2

dp_e

動的計画法

蟻本p60の01ナップサック問題その他2の類題?

O(nW)では 1011 となり、配列が長すぎてしまうため、工夫。

重さではなく、価値の配列にすれば、O(nv)で 107となり、計算可能になる。

pythonでは間に合わなかったため、c++で提出した。

一応、pythonコード

c++コード