编辑代码

#include <stdio.h>
#include <stdlib.h>
// 物品结构体
struct Item {
    int value;
    int weight;
    double ratio; // 单位重量价值比
};
// 比较函数，用于优先队列的排序
int compare(const void *a, const void *b) {
    double ratioA = ((struct Item *)a)->ratio;
    double ratioB = ((struct Item *)b)->ratio;

    return (ratioB > ratioA) - (ratioB < ratioA);
}
// 分支界限法解决0-1背包问题
int knapsackBranchBound(int W, int wt[], int val[], int n) {
    struct Item items[n];

    // 创建物品结构体数组，计算单位重量价值比
    for (int i = 0; i < n; i++) {
        items[i].value = val[i];
        items[i].weight = wt[i];
        items[i].ratio = (double)val[i] / wt[i];
    }

    // 按单位重量价值比排序物品
    qsort(items, n, sizeof(items[0]), compare);

    int currentWeight = 0; // 当前背包重量
    double finalValue = 0.0; // 最终价值

    // 依次选择物品放入背包
    for (int i = 0; i < n; i++) {
        // 如果当前物品重量加上背包当前重量仍然小于等于背包容量，则可全部放入
        if (currentWeight + items[i].weight <= W) {
            currentWeight += items[i].weight;
            finalValue += items[i].value;
        } else { // 否则，部分放入
            int remain = W - currentWeight;
            finalValue += items[i].ratio * remain;
            break;
        }
    }

    return finalValue;
}
int main() {
    int val[] = {60, 100, 120}; // 物品价值
    int wt[] = {10, 20, 30};    // 物品重量
    int W = 50;                 // 背包容量
    int n = sizeof(val) / sizeof(val[0]); // 物品数量
    double result = knapsackBranchBound(W, wt, val, n);
    printf("背包中物品的最大价值为：%.2lf\n", result);
    return 0;
}