43 lines
1.3 KiB
C
43 lines
1.3 KiB
C
#include <stdio.h>
|
|
#define MAX_CAPACITY 150
|
|
#define MAX_ITEMS 7
|
|
typedef struct {// 物品结构体，包含重量、价值和性价比
|
|
int weight;
|
|
int value;
|
|
double ratio; // 性价比
|
|
} Item;
|
|
void sortItems(Item items[], int n) {// 计算性价比并进行排序
|
|
for (int i = 0; i < n - 1; i++) {
|
|
for (int j = i + 1; j < n; j++) {
|
|
if (items[i].ratio < items[j].ratio) {
|
|
// 交换物品
|
|
Item temp = items[i];
|
|
items[i] = items[j];
|
|
items[j] = temp;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
// 初始化物品
|
|
Item items[MAX_ITEMS] = { {35, 10, 0}, {30, 40, 0}, {60, 30, 0},
|
|
{50, 50, 0}, {40, 35, 0}, {10, 40, 0}, {25, 30, 0} };
|
|
for (int i = 0; i < MAX_ITEMS; i++) { // 计算性价比
|
|
items[i].ratio = (double)items[i].value / items[i].weight;
|
|
}
|
|
sortItems(items, MAX_ITEMS);// 按性价比排序
|
|
int capacity = MAX_CAPACITY;
|
|
int maxValue = 0;
|
|
printf("背包装入物品:\n"); // 装入背包
|
|
for (int i = 0; i < MAX_ITEMS; i++) {
|
|
if (items[i].weight <= capacity) {
|
|
printf("重量为：%d的物品被选中了\n", items[i].weight);
|
|
maxValue += items[i].value;
|
|
capacity -= items[i].weight;
|
|
}
|
|
}
|
|
printf("最大价值为：%d\n", maxValue);
|
|
return 0;
|
|
}
|