编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 物品结构体
struct Item {
    char name[50];
    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);
}

// 分支界限法解决背包问题
double knapsackBranchBound(int W, int wt[], int val[], char names[][50], int n) {
    struct Item items[n];

    // 创建物品结构体数组，计算单位重量价值比
    for (int i = 0; i < n; i++) {
        strcpy(items[i].name, names[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;
            printf("将 %s 放入背包\n", items[i].name);
        } else { // 否则，部分放入
            int remain = W - currentWeight;
            finalValue += items[i].ratio * remain;
            printf("将 %s 的部分放入背包\n", items[i].name);
            break;
        }
    }

    return finalValue;
}

int main() {
    char names[][50] = {"苹果", "雪梨", "香蕉"}; // 物品名称
    int val[] = {50, 60, 70}; // 物品价值
    int wt[] = {20, 50, 30};    // 物品重量
    int W = 50;                 // 背包容量
    int n = sizeof(val) / sizeof(val[0]); // 物品数量
    double result = knapsackBranchBound(W, wt, val, names, n);
    printf("背包中物品的最大价值为：%.2lf\n", result);
    return 0;
}