01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp


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

#include <iostream>
#include <vector>

using std::vector;

int optimal_weight(int W, const vector<int> &w)
{
    int I = w.size();
    int *m = new int[(W + 1) * (I + 1)];

    int *current = &m[W + 2];
    int *not_taken = &m[1];

    // each item
    for (int i = 1; i <= I; i++) {
        int wi = w[i - 1];
        for (int k = 1; k <= W; k++) {
            if (k >= wi) {
                int taken = *(not_taken - wi) + wi;
                *current = ((taken > *not_taken) ? taken : *not_taken);
            } else
                *current = *not_taken;

            current++;
            not_taken++;
        }
        // skip first column
        current++;
        not_taken++;
    }

    /* for (int i = 0; i <= I; i++) { */
    /*     for (int k = 0; k <= W; k++) */
    /*         std::cout << m[(W +1) * i + k] << " "; */
    /*     std::cout << std::endl; */
    /* } */

    int ret = *(current - 2);

    delete [] m;

    return ret;
}

int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    std::cin >> w[i];
  }
  std::cout << optimal_weight(W, w) << '\n';
}