首页C语言分支限界法背包问题代码

C语言分支限界法背包问题代码

时间: 2023-12-25 09:05:07 浏览: 107

```c #include <stdio.h> #include <stdlib.h> typedef struct { int weight; // 物品重量 int value; // 物品价值 float ratio; // 物品价值与重量的比值 } Item; int compare(const void *a, const void *b) { Item *itemA = (Item *)a; Item *itemB = (Item *)b; return (itemB->ratio - itemA->ratio); } float knapsack(int capacity, Item items[], int n) { qsort(items, n, sizeof(Item), compare); // 按照物品价值与重量的比值进行降序排序 int currentWeight = 0; // 当前背包重量 float currentValue = 0; // 当前背包价值 for (int i = 0; i < n; i++) { if (currentWeight + items[i].weight <= capacity) { currentWeight += items[i].weight; currentValue += items[i].value; } else { int remainingCapacity = capacity - currentWeight; currentValue += items[i].ratio * remainingCapacity; break; } } return currentValue; } int main() { int capacity = 50; // 背包容量 int n = 5; // 物品数量 Item items[n]; items[0].weight = 10; items[0].value = 60; items[0].ratio = 6; items[1].weight = 20; items[1].value = 100; items[1].ratio = 5; items[2].weight = 30; items[2].value = 120; items[2].ratio = 4; items[3].weight = 40; items[3].value = 140; items[3].ratio = 3.5; items[4].weight = 50; items[4].value = 160; items[4].ratio = 3.2; float maxValue = knapsack(capacity, items, n); printf("Max value: %.2f\n", maxValue); return 0; } ```

阅读全文