C语言贪心算法：背包问题

郎哥
C语言
24天前
179热度
0评论

背包问题是什么？

想象一下，你准备去旅行，只带了一个容量有限的背包，但你有很多需要的物品想要带上。这些物品大小各异，价值也不一样，比如一本厚重但充满知识的旅行指南，轻便却能记录美好瞬间的相机，以及保暖但占空间的外套。如何在有限的背包容量下，装入最有价值的物品，让这次旅行更加完美？这就是生活中的背包问题。
在 C 语言算法领域，背包问题是一个经典的组合优化问题。给定一个固定容量的背包和一组物品，每个物品都有自己的重量和价值。我们的目标是从这组物品中选择一些放入背包，使得放入背包的物品总重量不超过背包的容量，并且总价值最大化。例如，背包容量为 5 千克，有三个物品：物品 A 重 2 千克，价值 3 元；物品 B 重 3 千克，价值 4 元；物品 C 重 1 千克，价值 2 元。我们要思考如何选择物品，才能让背包里的物品价值总和最大。

贪心算法的核心思想

贪心算法在对问题求解时，总是做出在当前看来是最好的选择。它的每个步骤都基于当前状态做出最优选择，试图找到解决整个问题的总体最优方法。贪心算法的特点是一步一步进行，常以当前情况为基础，根据某个优化测度作最优选择，不考虑各种可能的整体情况，省去为找最优解穷尽所有可能而耗费的大量时间。例如在活动安排问题中，假设有一系列活动，每个活动都有开始时间和结束时间，目标是选择尽可能多的不重叠活动。贪心算法的做法是每次选择结束时间最早的活动，这样就能尽可能地为后续活动腾出时间。
在解决背包问题时，贪心算法通常用于解决分数背包问题，即物品可以被部分拿走。具体步骤为：先计算每种物品的单位价值（每单位重量的价值），并按照单位价值排序。从单位价值最高的物品开始，依次考虑是否将该物品装入背包。如果该物品可以完全装入背包，则全部装入；如果装入后背包仍有剩余空间，则继续考虑下一个单位价值次高的物品，并重复上述步骤。例如背包容量为 10 千克，有三个物品：物品 A 重 2 千克，价值 6 元；物品 B 重 3 千克，价值 9 元；物品 C 重 4 千克，价值 8 元。计算单位价值后，物品 A 单位价值为 3 元 / 千克，物品 B 为 3 元 / 千克，物品 C 为 2 元 / 千克。按照贪心算法，先将物品 A 和物品 B 放入背包，此时背包还剩 5 千克空间，再放入物品 C 的一部分，这样就能使背包内物品总价值最大化。贪心算法在解决分数背包问题时简单高效，但它无法解决所有类型的背包问题，比如 0-1 背包问题（每个物品只能选择放入背包一次或不放入），因为贪心算法的选择策略可能导致不同结果，不一定能得到全局最优解。

背包问题的贪心算法实现步骤

准备数据

在解决背包问题前，首先要处理的数据是物品的重量、价值以及背包的容量。我们可以用 C 语言的结构体数组来存储这些数据。例如：

#include <stdio.h>

// 定义物品结构体
typedef struct {
int weight; // 物品重量
int value; // 物品价值
} Item;

int main() {
int n, W;
printf("请输入物品数量n和背包容量W：");
scanf("%d %d", &n, &W);

Item items[n];
printf("请依次输入每个物品的重量和价值：\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
}

// 后续代码将在这里继续实现
return 0;
}

在这段代码中，我们定义了一个Item结构体，用于存储每个物品的重量和价值。在main函数中，首先获取用户输入的物品数量n和背包容量W，然后创建一个大小为n的Item结构体数组items，并通过循环获取每个物品的重量和价值。
1.5.3.2.计算价值密度
计算每个物品的价值密度（价值与重量的比值）是贪心算法解决背包问题的关键步骤。价值密度能帮助我们衡量每个物品单位重量的价值大小，从而在选择物品放入背包时，优先选择价值密度高的物品，以达到在有限背包容量下最大化总价值的目的。在 C 语言中，计算价值密度的代码如下：

#include <stdio.h>

// 定义物品结构体
typedef struct {
int weight; // 物品重量
int value; // 物品价值
double density; // 价值密度
} Item;

int main() {
int n, W;
printf("请输入物品数量n和背包容量W：");
scanf("%d %d", &n, &W);

Item items[n];
printf("请依次输入每个物品的重量和价值：\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
items[i].density = (double)items[i].value / items[i].weight; // 计算价值密度
}

// 后续代码将在这里继续实现
return 0;
}

在上述代码中，我们在Item结构体中新增了一个density成员变量，用于存储每个物品的价值密度。在获取每个物品的重量和价值后，通过items[i].density = (double)items[i].value / items[i].weight;语句计算其价值密度。这里将items[i].value强制转换为double类型，是为了确保除法运算结果为浮点数，从而得到准确的价值密度。

排序

按照价值密度从大到小对物品进行排序，可以按照价值密度从高到低的顺序依次考虑将物品放入背包，这样能保证在每一步选择中，都优先选择当前价值密度最高的物品，符合贪心算法在每一步都做出局部最优选择的思想。在C语言中，可以使用qsort函数进行排序。qsort是 C 标准库中的一个通用排序函数，它需要一个比较函数来确定元素的排序顺序。下面是使用qsort函数对物品进行排序的代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义物品结构体
typedef struct {
int weight; // 物品重量
int value; // 物品价值
double density; // 价值密度
} Item;

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
Item *x = (Item *)a;
Item *y = (Item *)b;
if (x->density > y->density) return -1; // 降序排列，密度大的在前
else if (x->density < y->density) return 1;
else return 0;
}

int main() {
int n, W;
printf("请输入物品数量n和背包容量W：");
scanf("%d %d", &n, &W);

Item items[n];
printf("请依次输入每个物品的重量和价值：\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
items[i].density = (double)items[i].value / items[i].weight; // 计算价值密度
}

qsort(items, n, sizeof(Item), cmp); // 对物品按价值密度排序

// 后续代码将在这里继续实现
return 0;
}

在这段代码中，我们定义了一个cmp函数，作为qsort的比较函数。cmp函数比较两个Item结构体指针所指向的物品的价值密度，根据比较结果返回相应的值，以实现按价值密度从大到小的排序。然后，通过qsort(items, n, sizeof(Item), cmp);语句调用qsort函数对items数组进行排序，其中items是要排序的数组，n是数组元素个数，sizeof(Item)是每个元素的大小，cmp是比较函数。

选择物品放入背包

根据排序结果依次将物品放入背包。在这个过程中，需要从价值密度最高的物品开始考虑。对于每个物品，首先判断它能否完全放入背包，即判断物品的重量是否小于等于背包的剩余容量。如果能完全放入，就将该物品放入背包，同时更新背包的剩余容量和已放入物品的总价值。当背包剩余容量不足，无法完全放入当前物品时，再计算该物品能放入背包的部分，并将这部分物品放入背包，更新总价值，然后结束物品选择过程。以下是用 C 语言代码实现物品放入背包逻辑，并计算背包中物品总价值的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义物品结构体
typedef struct {
int weight; // 物品重量
int value; // 物品价值
double density; // 价值密度
} Item;

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
Item *x = (Item *)a;
Item *y = (Item *)b;
if (x->density > y->density) return -1; // 降序排列，密度大的在前
else if (x->density < y->density) return 1;
else return 0;
}

int main() {
int n, W;
printf("请输入物品数量n和背包容量W：");
scanf("%d %d", &n, &W);

Item items[n];
printf("请依次输入每个物品的重量和价值：\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
items[i].density = (double)items[i].value / items[i].weight; // 计算价值密度
}

qsort(items, n, sizeof(Item), cmp); // 对物品按价值密度排序

int cur_weight = 0; // 当前已放入背包的物品总重量
double cur_value = 0.0; // 当前已放入背包的物品总价值

for (int i = 0; i < n; i++) {
if (cur_weight + items[i].weight <= W) { // 物品能完全放入背包
cur_weight += items[i].weight;
cur_value += items[i].value;
} else { // 物品不能完全放入背包
int remain_weight = W - cur_weight;
cur_value += (double)remain_weight / items[i].weight * items[i].value;
break;
}
}

printf("放入背包的物品总价值为：%.2f\n", cur_value);

return 0;
}

在上述代码中，我们定义了cur_weight和cur_value分别用于记录当前已放入背包的物品总重量和总价值。通过for循环遍历排序后的items数组，在循环中进行物品放入背包的判断和操作。如果cur_weight + items[i].weight <= W，说明物品能完全放入背包，就更新cur_weight和cur_value 。否则计算剩余容量能放入当前物品的部分价值，更新cur_value并跳出循环。最后通过printf("放入背包的物品总价值为：%.2f\n", cur_value);输出放入背包的物品总价值，其中%.2f表示以浮点数形式输出，并保留两位小数。

完整代码

#include <stdio.h>
#include <stdlib.h>
// 定义物品结构体
typedef struct {
int weight; // 物品重量
int value; // 物品价值
double density; // 价值密度
} Item;
// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
Item *x = (Item *)a;
Item *y = (Item *)b;
if (x->density > y->density) return -1; // 降序排列，密度大的在前
else if (x->density < y->density) return 1;
else return 0;
}
int main() {
int n, W;
printf("请输入物品数量n和背包容量W：");
scanf("%d %d", &n, &W);
Item items[n];
printf("请依次输入每个物品的重量和价值：\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
items[i].density = (double)items[i].value / items[i].weight; // 计算价值密度
}
qsort(items, n, sizeof(Item), cmp); // 对物品按价值密度排序
int cur_weight = 0; // 当前已放入背包的物品总重量
double cur_value = 0.0; // 当前已放入背包的物品总价值
for (int i = 0; i < n; i++) {
if (cur_weight + items[i].weight <= W) { // 物品能完全放入背包
cur_weight += items[i].weight;
cur_value += items[i].value;
} else { // 物品不能完全放入背包
int remain_weight = W - cur_weight;
cur_value += (double)remain_weight / items[i].weight * items[i].value;
break;
}
}
printf("放入背包的物品总价值为：%.2f\n", cur_value);
return 0;
}

假设输入物品数量为 3，背包容量为 5，物品的重量和价值分别为：物品 1（重量 2，价值 3）、物品 2（重量 3，价值 4）、物品 3（重量 1，价值 2）。运行程序后，输出结果为：

请输入物品数量n和背包容量W：3 5
请依次输入每个物品的重量和价值：
2 3
3 4
1 2
放入背包的物品总价值为：6.00