c - Knapsack 1/0 实现需要解释

Question

我正在尝试理解 Knapsack 1/0 Problem 的这种动态编程方法但我没能得到算法。

有人能解释一下这个具体的实现吗，摘自Rosetta Code大部头书？

用一些注释更新代码会有很大帮助!

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

非常感谢，斯凯拉

Answer 1

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

它们分别对应于解决方案中索引为“idx”的项目不包括或包括的选择。

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

if (idx < 0)意味着没有更多的项目需要考虑，这是递归的结束

if (weight < item[idx].weight)检查是否有可能包含项目 idx .如果自身重量大于限制重量，则无法包含。

另请注意，这不是动态规划，而是一种生成所有可能的元素子集的简单递归算法(递归树在这里和那里被修剪)。