贪心算法
优点：简单,高效
1>.贪狼准则（核心）
a.贪婪准则计算过程每一步都要求是最优解（局部最优）
b.贪婪准则一旦被设计，中途不变
2>.贪婪准则并不一定能得到最优解，而只是近似最优
装箱问题
问题描述：
问题描述：有若干个体积为V的箱子，有N个体积不全相同的物品。
要求将所有物品都装入箱子，并且打开的箱子尽可能少。
求解思路：
贪心准则：a.将所有物品都按体积降序排列
b.每次取出一个物品（当前未装入物体中体积最大的物体）
遍历所有已经打开的箱子，将物品尽可能放入最早打开的箱子
存储：尾插链表
算法描述：a.创建物品信息并初始化
b.把所有物品按体积降序排列
c.装箱
d.输出
代码实现：
#include<stdio.h>
#include<stdlib.h>
#define V 10 // 每个箱子的体积
#define N 8 // 物品个数
//物品信息
typedef struct{
int gno; // 物品编号
int gv; // 物品体积
}ElemG;
//物品节点
typedef struct node{
int gno;
struct node *link; // 指向下个物品节点的指针
}GoodsLink;
//箱子节点
typedef struct box{
int Remainder; // 存放箱子剩余体积
GoodsLink *hg; // 指向存放物品节点的指针
struct box *next; // 指向下个箱子节点的指针
}BoxLink;
/*1.创建物品信息并初始化*/
void create(ElemG *g){
int a[N] = { 1, 2, 3, 4, 5, 6, 7, 8};
printf("物品体积：");
for(int i=0; i<N; i++){
g[i].gno = i+1;
g[i].gv = a[i];
printf("%d ",g[i].gv);
}
}
/*2.把所有物品按照体积降序排列*/
void sort( ElemG *g){
ElemG temp; // 用于变量交换
//冒牌排序
for(int i=0; i<N -1 ; i++){
for(int j= 0; j<N-1-i; j++ ){
if(g[j].gv < g[j+1].gv){
temp = g[j];
g[j] = g[j+1];
g[j+1] = temp;
}
}
}
}
/*3.装箱*/
BoxLink * packed( ElemG *g){
BoxLink *p, *hbox = NULL, *tail;
for(int i=0; i<N; i++){
/*3.1 遍历箱子链,找到可以放下当前物品的箱子*/
for(p=hbox; p!=NULL&&(p->Remainder)<g[i].gv; p=p->next);
/*3.2 创建新箱子并初始化*/
if(p==NULL){
p = (BoxLink*)malloc(sizeof(BoxLink));
p->Remainder = V;
p->hg = NULL;
p->next = NULL;
if(hbox==NULL)
hbox = tail = p;//创建第一个箱子
else
tail = tail->next = p;//将新节点挂上，并移动尾指针使其指到新节点上
}
/*3.3 开始装箱*/
p->Remainder = p->Remainder-g[i].gv;//计算箱子剩余的体积
//放物品
GoodsLink *ne, *q;
ne = (GoodsLink *)malloc(sizeof(GoodsLink)); // 创建一个物品节点
ne->gno = g[i].gno;
ne->link = NULL;
if(p->hg==NULL)//装的是新箱子
p->hg = ne;
else{ //装的是旧箱子
for(q=p->hg; q->link; q=q->link);// 向后遍历，找到最后一个物品节点。并将新节点挂到末尾
q->link = ne;
}
}
return hbox;
}
/*4.输出*/
void printBox(BoxLink *hbox)
{
GoodsLink *q;
BoxLink *p = (BoxLink *)malloc(sizeof(BoxLink));
int cut = 0;
for(p=hbox; p!=NULL; p = p->next){
printf("第%d个箱子: ",++cut);
for(q=p->hg; q; q=q->link)
printf("%5d",q->gno);
printf("\n");
}
delete p;
}
int main(void){
// 定义物品信息，并分配内存空间
ElemG *g;
g = (ElemG *)malloc(N*sizeof(ElemG));
//1.创建物品信息并初始化
create(g);
//2.把所有物品按照体积降序排列
sort(g);
//3.装箱
BoxLink *hbox = NULL;
hbox = packed( g);
//4. 输出放入物品后箱子的情况
printBox(hbox);
}
网友评论