编辑代码

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

typedef struct {
    int weight;
    int value;
} Item;

typedef struct {
    int level;
    int profit;
    int weight;
    int bound;
} Node;

int max(int a, int b) {
    return (a > b) ? a : b;
}

Node create_node(int level, int profit, int weight, int bound) {
    Node node;
    node.level = level;
    node.profit = profit;
    node.weight = weight;
    node.bound = bound;
    return node;
}

int bound(Node u, int n, int W, Item items[]) {
    if (u.weight >= W) {
        return 0;
    }

    int boundValue = u.profit;

    int j = u.level + 1;
    int totalWeight = u.weight;

    while (j < n && totalWeight + items[j].weight <= W) {
        totalWeight += items[j].weight;
        boundValue += items[j].value;
        j++;
    }

    if (j < n) {
        boundValue += (W - totalWeight) * items[j].value / items[j].weight;
    }

    return boundValue;
}

int knapsack(int W, Item items[], int n) {
    Node *queue = (Node *)malloc(sizeof(Node) * (n + 1));
    int maxProfit = 0;

    Node u, v;
    u.level = -1;
    u.profit = u.weight = 0;
    queue[0] = u;

    int i = 0;
    while (i >= 0) {
        u = queue[i--];

        if (u.level == n - 1) {
            continue;
        }

        v.level = u.level + 1;
        v.weight = u.weight + items[v.level].weight;
        v.profit = u.profit + items[v.level].value;

        if (v.weight <= W && v.profit > maxProfit) {
            maxProfit = v.profit;
        }

        v.bound = bound(v, n, W, items);

        if (v.bound > maxProfit) {
            queue[++i] = v;
        }

        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = bound(v, n, W, items);

        if (v.bound > maxProfit) {
            queue[++i] = v;
        }
    }

    free(queue);

    return maxProfit;
}

int main() {
    Item items[] = {{1, 20}, {2, 7}, {3, 19}, {4, 711}, {5, 6}};
    int n = sizeof(items) / sizeof(items[0]);
    int W = 15;
    int result = knapsack(W, items, n);
    printf("最大价值: %d\n", result);
    return 0;
}