贪心算法----装箱问题
程序员文章站
2022-06-04 10:52:26
...
贪心准则:
1.将一个问题的几步的每一步抽象出公共的最优解
2.一个问题只有一个贪心准则(问题求解时,贪心准则不能改变)
特点
不一定可以产生最优解
好处:
简单快速
需求描述:
有N个物品,体积V1,V2,V3,V4….Vn,若干个体积为v的箱子。
问题:把所有的物品装进箱子中,使得打开的箱子尽量小。
思路:
1.将所有的物品按照体积的降序排列
2.按照箱子的打开顺序遍历已打开的箱子,将物品装入一个较早打开的箱子中。
图示:
代码描述:
#include<stdio.h>
#include<stdlib.h>
#define V 10
//定义物品
typedef struct {
int gno;//商品编号
int gv;//商品体积
}EGoods;
//定义物品链
typedef struct goods{
int gno;//商品编号
int gv;//商品体积
struct goods *link;//商品链
}GoodsLink;
//箱子
typedef struct box{
int restv;//箱子剩余体积
GoodsLink *hg;//用来挂物品链
struct box *next;//箱子链
}BoxLink;
//将物品按体积的降序排序
void sort(EGoods g[], int len){
for (int i = 0; i < len - 1; i++){
for (int j = i + 1; j < len; j++){
if (g[i].gv < g[j].gv){
EGoods t = g[i];
g[i] = g[j];
g[j] = t;
}
}
}
}
//装箱函数
BoxLink* packingBox(EGoods g[], int len){
sort(g, len);
GoodsLink *tailgoods = NULL;
BoxLink *hbox = NULL, *pbox = NULL, *tailbox = NULL;
for (int i = 0; i < len; i++){
//通过循环找到物品应该放的箱子中
for (pbox = hbox; pbox&&pbox->restv < g[i].gv; pbox=pbox->next);
if (!pbox){
//如果该物品是第一个放入箱子中的
//之前打开的箱子都装不下当前物品
//打开新箱子
pbox = (BoxLink*)malloc(sizeof(BoxLink));
//初始化箱子
pbox->hg = NULL;
pbox->next = NULL;
pbox->restv = V;
if (!hbox)//如果是第一个箱子
{
hbox = pbox;
tailbox = pbox;
}
else{
tailbox->next = pbox;
tailbox = tailbox->next;
}
}
//生成当前物品
GoodsLink *newq = (GoodsLink*)malloc(sizeof(GoodsLink));
newq->gno = g[i].gno;
newq->gv = g[i].gv;
newq->link = NULL;
//利用循环找到当前物品在箱子中的位置(找到箱子链的为节点,之后进行挂链)
for (tailgoods = pbox->hg; tailgoods&&tailgoods->link; tailgoods = tailgoods->link);
if (!tailgoods){
pbox->hg = newq;
}
else{
tailgoods->link = newq;
}
pbox->restv -= g[i].gv;
}
return hbox;
}
//打印箱子
void print(BoxLink *hbox){
int count = 0;//记录箱子号
for (BoxLink *pb = hbox; pb; pb = pb->next){
printf("箱子号:%d\n",++count);
for (GoodsLink *pg = pb->hg; pg; pg = pg->link){
printf("物品编号:%d,体积:%d\t", pg->gno, pg->gv);
}
printf("\n");
}
}
int main(void){
int v[10] = { 3, 2, 5, 8, 4, 7, 6, 9, 1, 10 };
EGoods g[10];
for (int i = 0; i < 10; i++){
g[i].gno = i + 1;
g[i].gv = v[i];
}
print(packingBox(g, 10));
system("pause");
return 0;
}
运行结果:
上一篇: 最小二乘法实现