本文實(shí)例講述了C語(yǔ)言基于貪心算法解決裝箱問(wèn)題的方法。分享給大家供大家參考，具體如下：
問(wèn)題描述：
有一些箱子，容量為V，同時(shí)有n個(gè)物品，每個(gè)物品有一個(gè)體積（小于等于箱子容量），要求將物品全部裝入箱子中，使占用的箱子數(shù)盡量少。
貪心算法中要求每一步的解都是當(dāng)前步驟中的最優(yōu)解。原問(wèn)題的解可以通過(guò)一系列局部最優(yōu)的選擇來(lái)達(dá)到，這種選擇并不依賴于子問(wèn)題的解。
算法思想：
1、數(shù)據(jù)結(jié)構(gòu)
要求求解箱子數(shù)目，也就是說(shuō)不能確定會(huì)占用多少個(gè)箱子，因此采用鏈表的形式來(lái)存儲(chǔ)箱子及其信息。
同時(shí)，每個(gè)箱子中物品的數(shù)目也無(wú)法確定，同理采用鏈表來(lái)存儲(chǔ)每個(gè)箱子中的物品信息。
由此得出數(shù)據(jù)節(jié)點(diǎn)的定義：
typedef struct{ int gno; int gv;}Goods;typedef struct node{ int gno; struct node *link;}GNode;typedef struct node1{ int remainder; GNode * head; struct node1 * next;}GBox;2、求解思路
使打開(kāi)的箱子數(shù)盡量少，也就是說(shuō)每個(gè)箱子容積被盡可能多地占用。將物品按照體積降序排列后，再?gòu)牡谝粋€(gè)物品開(kāi)始，挨個(gè)尋找能放下它的箱子，這樣可以保證局部最優(yōu)。
void GoodsSort(Goods goods[], int n){ int i, j; Goods t; for (i = 0; i<n - 1; i++) { for (j = i + 1; j<n; j++) { if (goods[i].gv<goods[j].gv) { t = goods[i]; goods[i] = goods[j]; goods[j] = t; } } } for (i = 0; i<n; i++) printf("%d %d/n", goods[i].gno, goods[i].gv);排序完成，就可以正式開(kāi)始裝箱子了。
每次都從第一個(gè)箱子開(kāi)始，查看它的剩余容積還能不能放下當(dāng)前的物品，能放下最好咯，放不下的話就繼續(xù)查看下一個(gè)箱子的剩余容量。如果所有的已經(jīng)打開(kāi)的箱子都放不下當(dāng)前的物品，那就只好再打開(kāi)一個(gè)空箱子，把它塞進(jìn)去。
GBox * GoodsBox(Goods goods[], int n){ GNode *h = NULL, *pg, *t; GBox *hbox = NULL, *pb, *qb; int i; for (i = 0; i<n; i++)/////////////////遍歷貨物信息數(shù)組 { pg = (GNode *)malloc(sizeof(GNode));///////////////分配貨物節(jié)點(diǎn)單元 pg->gno = goods[i].gno; pg->link = NULL;//貨物節(jié)點(diǎn)初始化 if (!hbox)//若一個(gè)箱子都沒(méi)有 { hbox = (GBox *)malloc(sizeof(GBox)); hbox->remainder = 10; hbox->head = NULL; hbox->next = NULL; } qb=pb = hbox;//都指向箱子頭 while (pb)//找箱子 { if (pb->remainder >= goods[i].gv)/////////////////////////////能裝下 break;//找到箱子，跳出while else { qb = pb; pb = pb->next;//qb是前驅(qū) } }/////////////////////////////////////遍歷箱子結(jié)束 if (pb==NULL)/////////////////////需要新箱子 { pb = (GBox *)malloc(sizeof(GBox));//分配箱子 pb->head = NULL; pb->next = NULL; pb->remainder = 10;//初始體積 qb->next = pb;//前驅(qū)指上 } if (!pb->head)//如果箱子里沒(méi)貨 { pb->head = pg; t = pb->head; } else { t = pb->head; while (t->link) t = t->link;//貨尾 尾插 t->link = pg; } pb->remainder -= goods[i].gv; ////////////////////////////////////裝箱 } return hbox;希望本文所述對(duì)大家C語(yǔ)言程序設(shè)計(jì)有所幫助。
新聞熱點(diǎn)
疑難解答
圖片精選
