C++ Knapsack Problem dynamic programming

👍 g++ -std=c++11 knapsack_dyn.cpp
👍 ./a.out
24
👍 cat knapsack_dyn.cpp 
#include <iostream>
using namespace std;

typedef struct 
  { int size; int val; } Item;
Item A{3,  4}, B{4,  5}, C{7, 10},
     D{8, 11}, E{9, 13};
Item itms[]{A, B, C, D, E};

int N = 5;
int unknown = -1;
int maxKnown[18];

int knap(int M) {
  int i, sp, max, t;
  if (maxKnown[M] != unknown)
    return maxKnown[M];
  for (i = 0, max = 0; i < N; i++)
    if ((sp=M - itms[i].size)>=0)
      if((t=knap(sp)+itms[i].val)>max)
        max = t; 
  maxKnown[M] = max;
  return max;
}
    
int main() {
  for (int i = 0; i <= 17; i++)
    maxKnown[i] = unknown;
  cout << knap(17) << endl;
}

    

ch5.3 Dynamic Programming p250/229 of