Knapsack 1/0 Implementation needs explanation

Question

I'm trying to understand this dynamic programming approach to the Knapsack 1/0 Problem but i fail to get the algorithm.

Would somebody please be so kind as to explain this specific implementation, taken from Rosetta Code to me?

Updating the code with some comments would help a lot!

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

typedef struct {
        const char * name;
        int weight, value;
} item_t;

item_t item[] = {
        {"map",                     9,       150},
        {"compass",                 13,      35},
        {"water",                   153,     200},
        {"sandwich",                50,      160},
        {"glucose",                 15,      60},
        {"tin",                     68,      45},
        {"banana",                  27,      60},
        {"apple",                   39,      40},
        {"cheese",                  23,      30},
        {"beer",                    52,      10},
        {"suntancream",             11,      70},
        {"camera",                  32,      30},
        {"T-shirt",                 24,      15},
        {"trousers",                48,      10},
        {"umbrella",                73,      40},
        {"waterproof trousers",     42,      70},
        {"waterproof overclothes",  43,      75},
        {"note-case",               22,      80},
        {"sunglasses",              7,       20},
        {"towel",                   18,      12},
        {"socks",                   4,       50},
        {"book",                    30,      10}
};

#define n_items (sizeof(item)/sizeof(item_t))

typedef struct {
        uint32_t bits; /* 32 bits, can solve up to 32 items */
        int value;
} solution;


void optimal(int weight, int idx, solution *s)
{
        solution v1, v2;
        if (idx < 0) {
                s->bits = s->value = 0;
                return;
        }

        if (weight < item[idx].weight) {
                optimal(weight, idx - 1, s);
                return;
         }

        optimal(weight, idx - 1, &v1);
        optimal(weight - item[idx].weight, idx - 1, &v2);

        v2.value += item[idx].value;
        v2.bits |= (1 << idx);

        *s = (v1.value >= v2.value) ? v1 : v2;
}

int main(void)
{
        int i = 0, w = 0;
        solution s = {0, 0};
        optimal(400, n_items - 1, &s);

        for (i = 0; i < n_items; i++) {
                if (s.bits & (1 << i)) {
                        printf("%s\n", item[i].name);
                        w += item[i].weight;
                }
        }
        printf("Total value: %d; weight: %d\n", s.value, w);
        return 0;
}

Thanks a lot in advance, skylla

Answer 1

I don't understand exactly why solutions v1 and v2 are used, what they are used for

They correspond to the choices of not including or including, respectively, the item with index "idx" in the solution.

what the 2 if-conditions at the beginning of optimal() mean....

if (idx < 0) means simply there are no more items to consider, it's the end of the recursion

if (weight < item[idx].weight) checks the if it's possible at all to include item idx. It's not possible to include if its own weight is greater than the limit weight.

Also, note that this is not a dynamic programming, but a simple recursive algorithm that generates all possible subsets of elements (the recursion tree pruned here and there).