C语言贪心法：巧妙解决背包问题，实现价值最大化

```c #include <stdio.h> // 定义一个结构体来存储物品的信息 typedef struct { int weight; int value; int index; } Item; // 比较函数，用于排序 int compare(const void *a, const void *b) { Item *itemA = (Item *)a; Item *itemB = (Item *)b; // 按照单位价值从高到低排序 return (itemB->value / itemB->weight) - (itemA->value / itemA->weight); } int main() { int n; // 物品数量 scanf("%d", &n); Item items[n]; for (int i = 0; i < n; i++) { scanf("%d", &items[i].weight); items[i].index = i + 1; } for (int i = 0; i < n; i++) { scanf("%d", &items[i].value); } int capacity; // 背包容量 scanf("%d", &capacity); // 按照单位价值从高到低排序 qsort(items, n, sizeof(Item), compare); int totalWeight = 0; int totalValue = 0; int selectedItems[100]; // 存储选择的物品索引 int selectedItemCount = 0; // 选择物品 for (int i = 0; i < n; i++) { if (totalWeight + items[i].weight <= capacity) { totalWeight += items[i].weight; totalValue += items[i].value; selectedItems[selectedItemCount++] = items[i].index; } } // 输出结果 printf("选择物品: "); for (int i = 0; i < selectedItemCount; i++) { printf("%d ", selectedItems[i]); } printf("\n总重量: %d\n总价值: %d\n", totalWeight, totalValue); return 0; } ``` ### 需要注意的逻辑点： 1. **单位价值计算**：在排序时，按单位价值（即价值除以重量）从高到低排序，确保优先选择单位价值高的物品。 2. **容量限制**：在选择物品时，要确保当前选择的物品不会超过背包的容量。 3. **选择记录**：记录选择的物品索引，以便输出最终选择的物品列表。 ######[AI写代码神器 | 539点数解答 | 2024-11-27 08:36:20]