编辑代码

#include <stdio.h>
typedef struct {
    char name[20];
    int price;
    int weight;
    double valueWeightRatio; // 价值重量比
} Item;

// 交换两个物品的位置
void swap(Item *a, Item *b) {
    Item temp = *a;
    *a = *b;
    *b = temp;
}

// 按照价值重量比升序排序物品数组
void sortByValueWeightRatio(Item items[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (items[j].valueWeightRatio >= items[j + 1].valueWeightRatio) {
                swap(&items[j], &items[j + 1]);
            }
        }
    }
}

// 计算边界值
double calculateUpperValue(int currentValue, int remainingCapacity, Item items[], int n) {
    double upperValue = currentValue;
	
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= remainingCapacity) {
            upperValue += items[i].price;
            remainingCapacity -= items[i].weight;
        } else {
            upperValue += items[i].valueWeightRatio * remainingCapacity;
            break;
        }
    }

    return upperValue;
}

// 使用分支限界法求解背包问题
void knapsackBranchAndBound(Item items[], int n, int capacity, int currentWeight, int currentValue, int selectedItems[]) {
    static double maxValue = 0; // 记录最大价值
    if (currentWeight > capacity) {
        return; // 超过背包容量，返回
    }

    if (n == 0) {
        // 已经处理完所有物品，更新最大价值和所选取的物品
        if (currentValue > maxValue) {
            maxValue = currentValue;

            printf("选择了: ");
            for (int i = 0; i < 4; i++) {
                if (selectedItems[i] == 1) {
                    printf("%s ", items[i].name);
                }
            }
            printf("\n");

            printf("总价值: %d\n", currentValue);
        }
        return;
    }

    // 计算边界值
    double upperValue = calculateUpperValue(currentValue, capacity - currentWeight, items, n);

    // 若边界值小于当前最大价值，剪枝
    if (upperValue < maxValue) {
        return;
    }

    // 选择当前物品
    selectedItems[n - 1] = 1;
    knapsackBranchAndBound(items, n - 1, capacity, currentWeight + items[n - 1].weight, currentValue + items[n - 1].price, selectedItems);

    // 不选择当前物品
    selectedItems[n - 1] = 0;
    knapsackBranchAndBound(items, n - 1, capacity, currentWeight, currentValue, selectedItems);
}

int main() {
    Item items[] = {
        {"Iphone", 2000, 1, 0},
        {"吉他", 1500, 1, 0},
        {"音响", 3000, 4, 0},
        {"笔记本", 2000, 3, 0}
    };

    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 4;
    int selectedItems[n];
    sortByValueWeightRatio(items, n);
    knapsackBranchAndBound(items, n, capacity, 0, 0, selectedItems);
    printf("=======================================\n"); 

    return 0;
}