Binary decomposition

c[i] = 1 + 2 + 4 + … + 2^k + r. Create log₂(c[i]) new items with those quantities. Solve as 0/1.

Advertisement

Implementation

List items = new ArrayList<>(); // [weight, value]
for (int i = 0; i < n; i++) {
  int k = 1, remaining = count[i];
  while (k <= remaining) {
    items.add(new int[]{k * weight[i], k * value[i]});
    remaining -= k;
    k *= 2;
  }
  if (remaining > 0) items.add(new int[]{remaining * weight[i], remaining * value[i]});
}
// Then solve 0/1 knapsack on items
Advertisement

Complexity

O(N × log(max c) × W). Massive improvement over O(sum × W) when counts large.

Monotonic queue optimization

Advanced: O(N × W) using deque-based DP. Segments of weight partitioned by modulo.