一般背包问题
问题描述
想象你有一个背包，它最多可以放 M 公斤的物品。你面前有 n 个物品，每个物品的重量是 Wi，如果将这个物品完全放入背包，你将获得 Pi 的收益。
问题目标
你需要决定如何放置这些物品，以便在不超过背包容量的前提下，获得最大的收益。
问题类型
- 0/1背包问题：每个物品要么完全放入背包，要么完全不放。这种问题无法用贪心法求得最优解。
- 一般背包问题：物品可以分割，即你可以取物品的一部分放入背包。这种问题可以使用贪心法求得最优解。
解决方法
在一般背包问题中，我们采用贪心法来求解，具体步骤如下：
- 计算价值重量比：首先计算每个物品的 价值重量比，即 Pi/Wi。
- 排序：根据价值重量比，从高到低对物品进行排序。
- 选择物品：从价值重量比最高的物品开始，尽可能多地放入背包，直到背包装满或物品用尽。
小注释
- 一般背包问题允许物品分割，这意味着你可以取物品的一部分来实现最大价值，这与0-1背包问题不同。
特别提示
- 贪心法在一般背包问题中可以得到最优解，但在0-1背包问题中只能得到近似解。
贪心策略解析
在解决一般背包问题时，我们可以使用不同的贪心策略来尝试获得最大的背包总价值。以下是三种常见的贪心策略：
1. “价值最大”优先
- 策略描述：选择价值最高的物品优先放入背包。
- 优势：可以尽可能快地增加背包的总价值。
- 劣势：可能会导致背包容量消耗过快，从而减少装入背包的物品数量，影响目标函数的最大值。
2. “重量最轻”优先
- 策略描述：选择重量最轻的物品优先放入背包。
- 优势：可以装入尽可能多的物品，间接增加背包的总价值。
- 劣势：背包的价值增长可能不够迅速，因为轻的物品不一定价值高，这可能影响目标函数的最大值。
3. “单位重量价值最大”优先
- 策略描述：选择单位重量价值最大的物品优先放入背包。
- 单位重量价值 = 价值 / 重量
- 优势：
- 在背包价值增长和背包容量消耗之间寻找平衡。
- 确保在不牺牲背包容量的前提下，尽可能增加背包的总价值。
选择建议
- 推荐策略：通常选择“单位重量价值最大”优先的策略，因为它综合考虑了价值和重量，更有可能达到目标函数的最大值。
图解
物品的价值和重量如表2-3所示。如果背包容量 w = 50，怎么才能装入最大价值的物品？
物品清单
（1）贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行降序排列，排序后的物品清单如下所示：
排序后的物品清单
（2）按照贪心策略，每次选择单位重量价值大的物品装入背包。
求解步骤
第一次选择
- 物品3 的单位重量价值最大，为5。
- 背包容量：50kg > 10kg（物品3的总重量）
- 操作：物品3全部放入背包。
- 结果：背包容量剩余50-10=40kg，剩下物品2和物品1未放入。
第二次选择
- 在物品2和物品1中，物品2 的单位重量价值最大，为4。
- 背包容量：40kg > 30kg（物品2的总重量）
- 操作：物品2全部放入背包。
- 结果：背包容量剩余40-30=10kg，剩下物品1未放入。
第三次选择
- 考虑物品1，背包容量：10kg < 20kg（物品1的总重量）
- 操作：最多放一半的物品1（即10kg重量）。
- 结果：背包容量满，无法再放入更多物品。
总价值计算
- 物品1 放一半，价值为 60/2= 30
- 物品2 全部放入，价值为 120
- 物品3 全部放入，价值为 50
计算公式：
计算总价值
= 60*1/2(物品1放一半）+ 120（物品2全放）+50（物品3全放）
=30+120+50
=200
（3）构造最优解
通过贪心策略，我们成功地将总价值最大化至200，同时不超过背包的容量限制。
代码：
// 定义结构体Item，包含重量weight和价值value
typedef struct {
float weight; // 物品的重量
float value; // 物品的价值
} Item;
// compare函数用于比较两个Item对象，计算每个物品的价值密度（value/weight），并返回值较大的那一个
int compare(const void *a, const void *b) {
// 解压指针指向的Item对象
Item *itemA = (Item *)a;
Item *itemB = (Item *)b;
// 计算每个物品的密度，进行大小比较
float ratioA = itemA->value / itemA->weight;
float ratioB = itemB->value / itemB->weight;
// 比较结果返回大于、小于0分别代表排序后B应排在A前面
return (ratioB > ratioA) - (ratioB < ratioA);
}
// 函数Knapsack接收背包容量、物品数组、是否放入的标志数组和总价值输出指针
void Knapsack(int n, float capacity, Item items[], float x[], float *value) {
*value = 0.0; // 初始化总价值
// 对物品数组按照价值密度降序排列
qsort(items, n, sizeof(Item), compare);
// 遍历每个物品，如果不超过背包容量，则全部放入并更新容量和价值
for (int i = 0; i < n; i++) {
if (items[i].weight <= capacity) {
x[i] = 1; // 标记放入
*value += items[i].value; // 更新总价值
capacity -= items[i].weight; // 减少背包容量
} else { // 如果超过，只取部分放入
x[i] = capacity / items[i].weight; // 取整数部分放入
*value += items[i].value * x[i];
break; // 找到第一个合适的物品后停止
}
}
}
// 主函数，获取用户输入，创建并初始化数组，调用Knapsack函数，输出结果，并释放内存
int main() {
int n; // 物品数量
float capacity; // 背包容量
// 用户输入
printf("请输入背包的容量: ");
scanf("%f", &capacity);
printf("请输入物品的数量: ");
scanf("%d", &n);
// 动态分配存储空间
Item *items = (Item *)malloc(n * sizeof(Item));
float *x = (float *)malloc(n * sizeof(float));
// 输入每个物品的信息
for (int i = 0; i < n; i++) {
printf("请输入物品 %d 的重量: ", i + 1);
scanf("%f", &items[i].weight);
printf("请输入物品 %d 的价值: ", i + 1);
scanf("%f", &items[i].value);
}
// 调用Knapsack函数求解
float value;
Knapsack(n, capacity, items, x, &value);
// 输出结果
printf("最大价值: %f\n", value);
printf("物品选择: ");
for (int i = 0; i < n; i++) {
printf("%d ", (int)(x[i] * 10)); // 将浮点数转换为整数并保留一位小数显示
}
printf("\n");
// 释放动态分配的内存
free(items);
free(x);
return 0; // 程序结束
}