次のような動的計画法を考えます．

• \(\mathrm{dp}[w][j] \coloneqq\) 重み \(w\) 以下の品物から，重みの総和が \(j\) となるように選んだときの，うれしさの最大値

重みが \(w\) の品物をまとめて処理することを考えます．重みが \(w\) の品物が \(m\) 種類あり，価値はそれぞれ \(v_1,\dots,v_m\) であるとします．これらの品物から \(k\) 個選ぶときの，うれしさの総和の最大値 \(f_w(k)\) が求まっていたとすると，次のような遷移によって動的計画法のテーブルを更新することができます．

\[ \mathrm{dp}[w][j] \leftarrow \max\{\mathrm{dp}[w-1][j-kw] + f_w(k) \mid k=0,\dots,\lfloor j/w \rfloor\} \quad (j=0,\dots,W) \]

\(f_w(k)\) は貪欲法により求めることができます．価値 \(v\) の品物を \(k\) 個選んだときの嬉しさは \(k v - k^2 = \sum_{i=1}^k (v - 2i + 1)\) と書けます．この式は，「この品物を \(i\) 回目に選んだときに得られる追加のうれしさは \(v-2i+1\) である」と解釈できます．すると，「追加で得られるうれしさが最大の品物から選ぶ」という貪欲法で \(f_w(k)\) を求めることができます． 具体的には，以下のアルゴリズムを用いればよいです．

1. \(i=1,2,\dots,m\) について， \(d_i \leftarrow v_i-1\) とする
2. \(k=1,2,\dots,\lfloor W/w \rfloor\) について以下の操作を行う
   • \(d_1,\dots,d_m\) のうちの最大値 \(d_i\) を求める
   • \(f_w(k) \leftarrow f_w(k-1) + d_i\) とする
   • \(d_i \leftarrow d_i - 2\) とする

上のアルゴリズムは，優先度付きキューを用いて実装すれば \(O((N+W/w)\log N)\) 時間で動作します．

以上の解法の時間計算量を見積もりましょう．ボトルネックとなるのは，遷移を計算するところであり，一つの \(w\) に対する遷移の時間計算量は \(O(W^2/w)\) です．遷移の全体の計算量は \(O(\sum_{w=1}^W W^2/w) = O(W^2 \log W)\) となります．ここで，調和級数の関係 \(\sum_{w=1}^W 1/w = O(\log W)\) を用いました．

実装例 (Python)