// This program uses code from "Algorithms in C, Third Edition,"
//               by Robert Sedgewick, Addison-Wesley, 1998.

#include <stdio.h>
#include <stdlib.h>


struct Items
{
   int number;
   char ** types;
   int * weights; 
   int * values;
};


int knapsack(int max_weight, struct Items items)
{
   // Creating memory for the array of solutions.
   int * solutions = malloc(sizeof(int) * (max_weight + 1));
   int index;
   
   // Marking the solutions to all cases as "unknown".
   // We use the convention that -1 stands for "unknown".
   for (index = 0; index <= max_weight; index++)
   {
      solutions[index] = -1;
   }
   
   int result = knapsack_helper(max_weight, items, solutions);
   free(solutions);
   return result;
}


int knapsack_helper(int weight, struct Items items, int * solutions)
{
   // if problem already solved, return stored solution.
   if (solutions[weight] != -1)
   {
      return solutions[weight];
   }

   int result;
   
   // base case.
   if (weight == 0) result = 0;
   
   // recursive case
   else
   {
      int item;
      result = 0;
      for (item = 0; item < items.number; item++)
      {
         int rem = weight - items.weights[item];
         if (rem < 0) continue;
         int value = items.values[item] + knapsack_helper(rem, items, solutions);
         if (value > result) result = value;
      }
   }
   
   solutions[weight] = result;
   return result;
}


int main()
{
   struct Items items;
   items.number = 5;
   char * types[] = {"A", "B", "C", "D", "E"};
   items.types = types;
   int weights[] = {3, 4, 7, 8, 9};
   items.weights = weights;
   int values[] = {4, 5, 10, 11, 13};
   items.values = values;

   int N;
   while(1)
   {
      printf("Enter an integer N: ");
      scanf("%d", &N);
      if (N < 0) break;
      int f = knapsack(N, items);
      printf("    knapsack(N) = %d\n", f);
   }
   return 0; 
}