#include<stdio.h>
/** 0/1 knapsack problem **/
/***  Size    3     4     7     8     9
      value   4     5    10    11    13
      name    egg   bag  cat   dog   engle
*****/
#define NTYPE 5
#define MAX_SIZE 99
int size[NTYPE+1] = { 0, 3, 4, 7, 8, 9 };
int value[ ] = { 0,      4, 5,10,11,13 };
char name[ ][9] = { "null", "egg", "bag", "cat", "dog", "engle" };
int cost[ MAX_SIZE + 1];
int best[ MAX_SIZE + 1];
int i,j,k,m,n; char tmp[99];
int capacity, totval, totsize;
int main(){
    for(i=1; i<= MAX_SIZE; ++i) { cost[i] = 0; best[i] =0; }
    for(j=1; j<= NTYPE; ++j){
       for(i=1; i<= MAX_SIZE; ++i){
          if(i >= size[j])
            if(cost[i] < cost[i-size[j]] + value[j]) {
                cost[i] = cost[i-size[j]] + value[j];
                best[i] = j;   /* j-th object */
            }
       }
    }
    while(1){
        printf("capacity=? ");
        gets(tmp); capacity = atol(tmp);
        if(capacity<=0) break;
        totval= totsize = 0;
        while(capacity >=0) {
            k = best[capacity]; if(k<=0) break;
            printf( "%s\t %2d\n", name[k], value[k]);
            capacity -= size[k];
            totsize   += size[k];
            totval   += value[k];
        }
        printf("===Total value=%d, total size=%d\n", totval, totsize);
    }
    return 0;
}