编辑代码

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

typedef struct {
    int value;
    int weight;
    float ratio; // 性价比，即单位重量的价值
} Item;

int compare(const void* a, const void* b) {
    const Item* item1 = (const Item*)a;
    const Item* item2 = (const Item*)b;
    return (item2->ratio - item1->ratio);
}

float bound(int n, int capacity, Item* items, int level, int value, int weight) {
    if (weight >= capacity) {
        return 0;
    }
    float result = value;
    int i = level;
    while (i < n && weight + items[i].weight <= capacity) {
        weight += items[i].weight;
        value += items[i].value;
        i++;
    }
    if (i < n) {
        result += (capacity - weight) * items[i].ratio;
    }
    return result;
}

int knapsack(int n, int capacity, Item* items) {
    qsort(items, n, sizeof(Item), compare);

    int max_value = 0;
    int current_value = 0;
    int current_weight = 0;
    int level = 0;

    int* solution = (int*)malloc(n * sizeof(int));
    float max_bound = bound(n, capacity, items, level, current_value, current_weight);

    while (level >= 0) {
        while (level < n && current_weight + items[level].weight <= capacity) {
            current_weight += items[level].weight;
            current_value += items[level].value;
            solution[level] = 1;
            level++;
        }

        if (level == n) {
            if (current_value > max_value) {
                max_value = current_value;
            }
            level--;
            current_weight -= items[level].weight;
            current_value -= items[level].value;
            solution[level] = 0;
            level--;
        } else {
            float new_bound = bound(n, capacity, items, level, current_value, current_weight);
            if (new_bound > max_bound) {
                level++;
                max_bound = new_bound;
            } else {
                level--;
                current_weight -= items[level].weight;
                current_value -= items[level].value;
                solution[level] = 0;
            }
        }
    }

    free(solution);
    return max_value;
}

int main() {
    int n = 5; // 物品数量
    int capacity = 10; // 背包容量

    Item items[] = {
        {60, 5}, // 物品1的价值和重量
        {50, 3}, // 物品2的价值和重量
        {70, 4}, // 物品3的价值和重量
        {30, 2}, // 物品4的价值和重量
        {40, 1}  // 物品5的价值和重量
    };

    int max_value = knapsack(n, capacity, items);
    printf("Maximum value: %d\n", max_value);

    return 0;
}