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