1.2.8 0-1 Knapsack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*

Solves the 0-1 knapsack problem: given items with nonnegative integer weights and values, choose
each item at most once to maximize total value without exceeding a capacity limit.

The one-dimensional dynamic programming array `dp[w]` stores the best value that can be achieved
with total weight at most `w` after processing some prefix of the items. Iterating weights in
decreasing order is what enforces the 0-1 constraint; it prevents the same item from being reused
during the current item update.

- `knapsack_01(weight, value, capacity)` returns a pair (`best_value`, `items`) containing the
  maximum value and the selected item indices in increasing order, where item `i` has weight
  `weight[i]` and value `value[i]`. All weights must be nonnegative integers. Items with weight $0$
  are allowed and can each be taken once. The take/skip decision for every item and capacity is
  stored to reconstruct the optimal subset.

Time Complexity:
- O(n*W) per call, where $n$ is the number of items and $W$ is the capacity.

Space Complexity:
- O(n*W) auxiliary.

*/

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

std::pair<int64_t, std::vector<int>> knapsack_01(
    const std::vector<int> &weight, const std::vector<int64_t> &value, int capacity
) {
  int n = static_cast<int>(weight.size());
  assert(static_cast<int>(value.size()) == n && capacity >= 0);
  for (int i = 0; i < n; i++) {
    assert(weight[i] >= 0 && value[i] >= 0);
  }
  std::vector<int64_t> dp(capacity + 1);
  std::vector<std::vector<char>> take(n, std::vector<char>(capacity + 1));
  for (int i = 0; i < n; i++) {
    for (int w = capacity; w >= weight[i]; w--) {
      int64_t candidate = dp[w - weight[i]] + value[i];  // Overflow warning.
      if (dp[w] < candidate) {
        dp[w] = candidate;
        take[i][w] = true;
      }
    }
  }
  // Optional: reconstruct one optimal subset.
  std::vector<int> items;
  for (int i = n - 1, w = capacity; i >= 0; i--) {
    if (take[i][w]) {
      items.push_back(i);
      w -= weight[i];
    }
  }
  std::reverse(items.begin(), items.end());
  return {dp[capacity], items};
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  vector<int> weight{3, 4, 5, 9};
  vector<int64_t> value{4, 5, 7, 10};
  auto [best_value, items] = knapsack_01(weight, value, 8);
  assert(best_value == 11);
  assert((items == vector<int>{0, 2}));
  return 0;
}