knapsack_problem.c

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

#define N 5
int size[N] = {2, 3, 5, 6, 9};
int value[N] = {2, 4, 7, 10, 14};

#define NAP_SIZE 16

typedef struct knapsack {
    int value;
    int item_num[N];
} KNAPSACK;

int main(void)
{
    KNAPSACK knapsack[NAP_SIZE + 1];
    int i, j, k, new_value;

    memset(knapsack, 0, sizeof(KNAPSACK) * (NAP_SIZE + 1));

    for (i = 0; i < N; i++) {
        for (j = size[i]; j < NAP_SIZE + 1; j++) {
            new_value = value[i] + knapsack[j - size[i]].value;
            if ( new_value > knapsack[j].value ) {
                knapsack[j].value = new_value;

                memcpy(knapsack[j].item_num, knapsack[j - size[i]].item_num, sizeof(int) * N);
                knapsack[j].item_num[i]++;
            }

        }
        for (j = 1; j <= NAP_SIZE; j++) {
            printf("%2d ", knapsack[j].value);
        }
        printf("\n");
    }
   
    printf("when NAP_SIZE is %d...\n", NAP_SIZE);
    for (i = 0; i < N; i++) {
        printf("item[%d]: %d\n", i + 1, knapsack[NAP_SIZE].item_num[i]);
    }

    return EXIT_SUCCESS;
}

/*
 0  2  2  4  4  6  6  8  8 10 10 12 12 14 14 16
 0  2  4  4  6  8  8 10 12 12 14 16 16 18 20 20
 0  2  4  4  7  8  9 11 12 14 15 16 18 19 21 22
 0  2  4  4  7 10 10 12 14 14 17 20 20 22 24 24
 0  2  4  4  7 10 10 12 14 14 17 20 20 22 24 24
when NAP_SIZE is 16...
item[1]: 0
item[2]: 0
item[3]: 2
item[4]: 1
item[5]: 0
 */