// 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)
{
   if (max_weight == 0) return 0;
   int max_value = 0;
   int i;
   for (i = 0; i < items.number; i++)
   {
      int rem = max_weight - items.weights[i];
      if (rem < 0) continue;
      int value = items.values[i] + knapsack(rem, items);
      if (value > max_value) max_value = value;
   }
   return max_value;   
}


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; 
}