#include <iostream>

using namespace std;

int main() {
  const int N = 3;              // the number of items
  const int Capacity = 10;      // the volumn of knapsack
  int weight[N + 1] = {-1, 3, 4, 5}; // the volumn of i-th item (index starting from 1)
  int value[N + 1] = {-1, 4, 5, 6};  // the value of i-th item
  int F[N + 1][Capacity + 1] = {0};  // status

  for (int i = 1; i <= N; i++) { // as for i-th item
    for (int j = 0; j <= Capacity; j++) {
      F[i][j] = F[i - 1][j]; // do not choose i-th item (default)
      if (j - weight[i] >= 0 &&
          F[i][j] < F[i - 1][j - weight[i]] + value[i]) { // if value is higher, then choose i-th item
        F[i][j] = F[i - 1][j - weight[i]] + value[i];
      }
    }
  }

  cout << "Max value: " << F[N][Capacity] << endl; // in this case: 11

  cout << "Status: " << endl;
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= Capacity; j++) {
        printf("%2d ", F[i][j]);
    }
    cout << endl;
  }

  return 0;
}