Knapsack(個数制限なしナップサック問題)
(dp/knapsack.hpp)
概要
個数制限なしナップサック問題を次に示す.
重さ $w_i$, 価値 $v_i$ であるような $N$ 種類の品物がある. 重さの和が $W$ 以下となるように選ぶとき, 価値の最大値を求めよ.
-
knapsack(w, v, W, NG, comp)
: W
以下の範囲で, 各重さについて価値の最大値を求める. NG
は到達ができない場合の値で, comp
は比較演算子.
計算量
Verified with
Code
Back to top page