《计算机算法设计与分析》电子工业出版社·第4版 算法分析题 3-3

a3-3.c

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

static const int B = 10;   // Bag volume
static const int N = 5;    // Item number
static const int A[] = {1, 2, 3, 4, 5};    // Item weight
static const int C[] = {3, 3, 3, 3, 3};    // Item value

static void knapsack_r(int *m, int *x) {
    // Use variable from global.
    int i, j, k;
    int max_m, max_x;

    k = N-1;
    for (i = 0; i <= B; i++) {
        int index = k*(B+1) + i;
        x[index] = i / A[k];
        m[index] = x[index] * C[k];
    }

    int tmp;
    for (k = N-2; k >= 0; k--) {
        for (i = 0; i <= B; i++) {
            // Exhaust adding [0:n] items to bag
            max_x = -1;
            max_m = -1;
            for (j = 0; (i - A[k]*j) >= 0; j++) {
                tmp = (k+1)*(B+1) + i - A[k]*j;
                if ((m[tmp] + j*C[k]) > max_m) {
                    max_m = m[tmp] + j*C[k];
                    max_x = j;
                }
            }
            m[k*(B+1) + i] = max_m;
            x[k*(B+1) + i] = max_x;
        }
    }

    // Output
    int res = B;
    for (k = 0; k < N; k++) {
        j = k*(B+1) + res;
        if (x[j] > 0) {
            printf("%d %d\n", k+1, x[j]);
            res -= A[k] * x[j];
        }
    }
}

int main(int argc, char **argv) {
    int i, k;

    // init
    k = (B+1)*N;
     int *m = malloc(k * sizeof(int)); // max value of [n,b]
     int *x = malloc(k * sizeof(int)); // item amount of [n,b]
    for (i = 0; i < k; i++) {
        m[i] = -1;
        x[i] = -1;
    }

    knapsack_r(m, x);

    // release
    free(m);
    free(x);
    return 0;
}