Unbounded Knapsack — Unlimited Copies

Recurrence

dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) for each item i, in forward-w order.

Implementation

int unboundedKnapsack(int W, int[] weight, int[] value) {
  int[] dp = new int[W + 1];
  for (int i = 0; i < weight.length; i++)
    for (int w = weight[i]; w <= W; w++)
      dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
  return dp[W];
}

vs 0/1

0/1: reverse w order to avoid reusing. Unbounded: forward w order to allow reuse.

Applications

Coin change. Cutting stock. Resource allocation with continuous supply.