编辑代码

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

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

Item items[] = {
    {10, 60},
    {20, 100},
    {30, 120},
};

int capacity = 50;
int numItems = sizeof(items) / sizeof(items[0]);
int maxProfit = 0;
int *bestItems = NULL;

int compare(const void *a, const void *b) {
    Item *itemA = (Item *)a;
    Item *itemB = (Item *)b;
    double ratioA = (double)itemA->profit / itemA->weight;
    double ratioB = (double)itemB->profit / itemB->weight;
    if (ratioA > ratioB) {
        return -1;
    } else if (ratioA < ratioB) {
        return 1;
    } else {
        return 0;
    }
}

int bound(int level, int weight, int profit) {
    if (weight > capacity) {
        return 0;
    }
    int remainingWeight = capacity - weight;
    for (int i = level + 1; i < numItems; i++) {
        if (items[i].weight <= remainingWeight) {
            profit += items[i].profit;
            remainingWeight -= items[i].weight;
        } else {
            profit += (double)remainingWeight / items[i].weight * items[i].profit;
            break;
        }
    }
    return profit;
}

void knapsackBranchBound(int level, int weight, int profit, int *selectedItems) {
    if (level == numItems) {
        if (profit > maxProfit) {
            maxProfit = profit;
            for (int i = 0; i < numItems; i++) {
                bestItems[i] = selectedItems[i];
            }
        }
        return;
    }
    if (weight + items[level].weight <= capacity) {
        selectedItems[level] = 1;
        knapsackBranchBound(level + 1, weight + items[level].weight,
                            profit + items[level].profit, selectedItems);
        selectedItems[level] = 0;
    }
    if (bound(level, weight, profit) > maxProfit) {
        knapsackBranchBound(level + 1, weight, profit, selectedItems);
    }
}

int main() {
    bestItems = (int *)malloc(numItems * sizeof(int));
    knapsackBranchBound(0, 0, 0, bestItems);

    printf("最大价值为: %d\n", maxProfit);
    printf("所选物品: ");
    for (int i = 0; i < numItems; i++) {
        if (bestItems[i] == 1) {
            printf("%d ", i);
        }
    }
    printf("\n");

    free(bestItems);
    return 0;
}