AOJ の 組み合わせ最適化コース の 個数制限付きナップザック問題 II の解説が見当たらないため、以下に自分なりの解説を書いておきます。
問題
解説
着想
品物 $i$, $j$ について、品物 $i$ を $v_j$ 個増やす代わりに、品物 $j$ を $v_i$ 個減らす操作を考えます。
$v_i / w_i > v_j / w_j$ であれば、価値の総和を変えることなく ( $v_i v_j - v_j v_i =0$ )、重さの総和を減らす ($w_i v_j - w_j v_i <0$) ことができます。
本問題の最適解である、「価値の総和が最大となる品物の選び方」に対して、重さの総和を単調減少させるように、上記の操作を繰り返し行います。
操作を繰り返すと、各品物が以下の3通りのどれかを満たすように、最適解を変形できます。
- なるべく使う品物（可能な限り増やす）
- なるべく使わない品物（可能な限り減らす）
- 半端に使う品物（上記のどちらでもない）
ただし、「なるべく使う品物」「なるべく使わない品物」に関しては、操作の都合上、一度に品物を $v_{max}$ 個増やす・減らす操作を行うことを考えると、最大で $v_{max} - 1$ 個の余りが発生することが分かります。
また、「半端に使う品物」は最大1種類の品物となるよう調整します。そのために、$v_i / w_i = v_j / w_j$ を満たす品物 $i$, $j$ が存在する場合は、品物どうしに何らかの優先順位を持たせるものとします。
最適解の範囲
ここまでの情報をまとめると、最適解は以下の範囲に存在することが分かります。
各品物を使う個数を $k_i$ として、
- なるべく使う品物の場合
- $\max(0, m_i - v_{max}) \le k_i \le m_i$
- なるべく使わない品物の場合
- $0 \le k_i \le \min(m_i, v_{max})$
- 半端に使う品物の場合
- $0 \le k_i \le m_i$
ただし、$v_i / w_i$ の値で比較したときに、
$ \lbrace なるべく使う品物 \rbrace \ge \lbrace 半端に使う品物 \rbrace \ge \lbrace なるべく使わない品物 \rbrace $
を満たすものとします。
２つの問題に分割
先ほどの最適解の各品物の個数 $k_i$ ですが、$p_i$, $q_i$ を下記のように定義して、$k_i = p_i + q_i$ を満たすように書き直します。
- なるべく使う品物の場合
- $0 \le p_i \le \min(m_i, v_{max})$
- $q_i = m_i - \min(m_i, v_{max})$
- なるべく使わない品物の場合
- $0 \le p_i \le \min(m_i, v_{max})$
- $q_i = 0$
- 半端に使う品物の場合
- $0 \le p_i \le \min(m_i, v_{max})$
- $0 \le q_i \le m_i - \min(m_i, v_{max})$
ここで、$p_i$ と $q_i$ をそれぞれ別の問題として考えます。
$p_i$ については、重さの最大値が $\Sigma_i w_i p_i$、最大個数が $\min(m_i, v_{max})$ である個数制限付きナップサック問題と同じ制約であることが分かります。また、$k_i$ が最適解であることから、$p_i$ もこの制約において価値の総和が最大となる選び方であると分かります。
（つまり、$p_i$ はこの制約の個数制限付きナップサック問題の最適解です。）
$q_i$ については、「半端に使う品物」を可能な限り使うことで、価値の総和を最大にできます。別の見方をすると、 全種類の $m_i - \min(m_i, v_{max})$ 個の品物に対して、重さの合計が $W - \Sigma_i w_i p_i$ を超えないように、$v_i / w_i$ の値が大きい順に貪欲法で選んだ結果とみなすことができます。
したがって、最適解の $\Sigma_{i} w_i p_i$ の値が分かっている場合、$p_i$ と $q_i$ についてそれぞれ解くことで、全体の最適解 $k_i = p_i + q_i$ を求めることができます。
実装
$p_i$ の個数制限付きナップサック問題の解き方ですが、価値の総和の最大値が $N \cdot (v_{max})^2$ と小さいため、スライド最小値を利用したDP（蟻本の302ページに記載）で解くことができます。
このDPの定義は以下のようになります。
$$dp[n]:=価値の総和がn以上となるように選んだ時の重さの総和の最小値$$
上記の $dp[n]$ は $\Sigma_{i} w_i p_i$ と同義であり、$n$ の値を決めると $p_i$ に関する重さの総和の値が一意に定まることを示しています。また、$q_i$ に関する問題も、残る容量を $W-dp[n]$ として貪欲法で解くことができます。したがって、$n$ の値を決めると $p_i$,$q_i$ に関する問題の価値の和を求めることができます。
$0 \le n \le N \cdot (v_{max})^2$ の範囲で $n$ を変化させて価値の和の最大値を調べることで、最終的な答えを得ることができます。計算量はDPを求める部分がネックとなり、$O(N^2 \cdot (v_{max})^2)$ となります。
実装例