Consider the following Dynamic Programming (DP):

• \(\mathrm{dp}[w][j] \coloneqq\) the maximum total happiness when choosing items with a total weight of \(j\), chosen from the items with weight \(w\) or less

Let us try to process items with weight \(w\) at once. Suppose that there are \(m\) types of items with weight \(w\), with their value being \(v_1,\dots,v_m\). If we know \(f_w(k)\), the maximum total happiness to choose \(k\) items from them, then we can update the DP table by the following transition:

\[ \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)\) can be found greedily. The happiness when choosing \(k\) items of value \(v\) can be written as \(k v - k^2 = \sum_{i=1}^k (v - 2i + 1)\). We can interpret this equation as follows: when this item is chosen for the \(i\)-th time, an additional happiness of \(v-2i+1\) is accumulated. This is why the following greedy algorithm is valid: choose the item with the maximum delta of happiness. Specifically, we can use the following algorithm:

1. For \(i=1,2,\dots,m\), let \(d_i \leftarrow v_i-1\).
2. For \(k=1,2,\dots,\lfloor W/w \rfloor\), do the following:
   • Find the maximum value \(d_i\) among \(d_1,\dots,d_m\).
   • Let \(f_w(k) \leftarrow f_w(k-1) + d_i\).
   • Let \(d_i \leftarrow d_i - 2\).

The algorithm above works in a total of \(O((N+W/w)\log N)\) time using a priority queue.

Let us estimate the time complexity of the solution above. The bottleneck part is the transition process, which costs \(O(W^2/w)\) time per single transition. The overall time complexity of the transition is \(O(\sum_{w=1}^W W^2/w) = O(W^2 \log W)\), where the harmonic series relation \(\sum_{w=1}^W 1/w = O(\log W)\) has been employed.

Sample code (Python)