## Problem

Given $N$ objects, the $i$’th of which weighs $ws_i$, values $vs_i$, and has $cs_i$ instances, we are to maximize the total value of a subset of the available instances whose total weight is less than or equal to $W$.

## Naive solution

dp[i][w] := Maximum total value composing of the first $i$ objects of total weight $w$.

The transition is simple:

dp[i][w] = max { dp[i - 1][w - k * ws[i]] + k * vs[i], k $\in$ [0, cs[i]] }

The time complexity is obviously O(N W max{ cs }).

## Observations

dp[i][w] = max { dp[i - 1][w - k * ws[i]] + k * vs[i], k $\in$ [0, cs[i]] } = max { dp[i - 1][w - 0 * ws[i]] + 0 * vs[i], dp[i - 1][w - 1 * ws[i]] + 1 * vs[i], …, dp[i - 1][w - x * ws[i]] + x * vs[i] }

Let $r$ = w - x * ws[i], and assume for an ephemeral convenience that 0 <= r < ws[i].

=>

dp[i][w] = dp[i][r + x * ws[i]] = max { dp[i - 1][r + j * ws[i]] + (x - j) * vs[i], j $\in$ [0, x] } = max { dp[i - 1][r + j * ws[i]] - j * vs[i], j $\in$ [0, x] } + x * vs[i]

If we fix $r$, we can update dp[i] from dp[i - 1] in linear time to $W$. Specifically, dp[i][r + x * ws[i]] needs to know only max { dp[i - 1][r + j * ws[i]] - j * vs[i], j $\in$ [0, x] }, which is independent of $x$, as long as $x$ is updated in increasing order.

However, it may not be the case that 0 <= $r$ < ws[i]. This happens when $x > cs_i$, in which case we are interested in max { dp[i - 1][r + j * ws[i]] - j * vs[i], j $\in$ [x - cs[i], x] }. the difference of which is only that some candidates get “outdated” as $x$ increases.

To deal with such cases, we can apply deque optimization to maintain the best “working” candidates.