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.

Solution

template<typename T, T INF = 0x3f3f3f3f>
vector<T> multiKnapsack( // O(n W)
  const int W, const vector<int> &ws, const vector<T> &vs, const vector<int> &cs) {
  vector<T> dp(W + 1, -INF); {
    dp[0] = 0;
    for (int i = 0; i < (int) ws.size(); ++i) {
      for (int r = 0; r < ws[i]; ++r) {
        deque<pair<T, int>> dq;
        for (int k = r; k <= W; k += ws[i]) {
          while (dq.size() && (k - dq.front().second) > ws[i] * cs[i]) dq.pop_front();
          while (dq.size() && dq.back().first <= dp[k] - vs[i] * (k / ws[i] + 1)) {
            dq.pop_back();
          }
          dq.emplace_back(dp[k] - vs[i] * (k / ws[i] + 1), k);
          if (dq.front().second < k) {
            dp[k] = max(dp[k], dq.front().first + vs[i] * (k / ws[i] + 1));
          }
        }
      }
    }
  }
  return dp;
}