[置頂] 裝箱問題
來源：程序員人生 發布時間：2014-12-13 09:02:42 閱讀次數：3566次
1 問題分析
這次我聽老范了講了裝箱的問題，題目：有n個物品，體積為v1，v2，v3. . .然后要求用最少的箱子把這些物品里面，這個是基于貪心算法的思想。貪心算法呢，就是每次找到的都是當前最優的，但是最后從整體情況看，它不1定是最優的；貪心算法規則1旦建立，就不能更改。1般情況下貪心算法求的解都是最優解。、
我們先對物品進行從大到小進行排序，每次拿出1個物品從第1個箱子開始遍歷，如果可以放下，那末重新拿出1個物品在從第1個開始遍歷，如果放不下，那末我們就開1個新箱子，將這個物品放在里面。其實這個思想很簡單的，最簡單的說我每次拿出1個物品都是從第1個箱子開始，放的下，拿下1個物品，放不下，開新箱子，每次遍歷的是箱子。
還有1種思路呢，就是每次遍歷的是物品。意思就是呢，我拿出1個箱子，開始遍歷物品（物品體積都是從大到小），遍歷完1次物品后第1個箱子就表示裝滿了，然后在開辟第2個箱子，知道所有的物品裝完為止。
存儲 ： 對物品個數我們是固定的的，可以用數組來寄存。而對箱子呢，我們不知道到底要用多少個箱子，因此呢箱子的個數我們用鏈表去寄存。每一個箱子里面裝的物品個數也不肯定，那末也用鏈表來處理。我們可以用3個結構體，第1個結構體箱子信息，第2個結構體物品信息，第3個結構體箱子中的物品的信息
2 代碼區
#include <iostream>
#include<stdlib.h>
#define null NULL
#define V 10
typedef struct{ //物品信息的結構體
int go; //編號
int gv; //體積
}GOODS;
typedef struct Gnode{ // 物品節點
int gnum; // 掛在鏈上的編號
struct Gnode *link; //指向下1個物品節點
}GNODE;
typedef struct Gbox{ // 箱子結構體
int reminder; //剩余空間
GNODE *head; // 指向物品節點的第1個節點
struct Gbox *next;
}GBOX;
void sortvolume(GOODS *goods,int n){ //排序
int i,j;
GOODS t;
for(i=0;i<n⑴;i++)
for(j=i;j<n;j++)
if(goods[i].gv<goods[j].gv)
{
t=goods[i];
goods[i]=goods[j];
goods[j]=t;
}
}
GBOX *packingbox(GOODS *goods,int n){ //具體實現裝箱
int i;
GBOX *hb=null,*ht,*p;
GNODE *newg,*q;
for(i=0;i<n;i++){
newg=(GNODE*)malloc(sizeof(GNODE));
newg->gnum=goods[i].go;
newg->link=null;
for(p=hb;p&&p->reminder<goods[i].gv;p=p->next); //p停下來時1定的總是開辟新箱子，分號注意
if(!p)
{
p=(GBOX *)malloc(sizeof(GBOX));
p->head=null;
p->next=null;
p->reminder=V;
if(!hb)
hb=ht=p;
else
ht=ht->next=p;
}
p->reminder-= goods[i].gv;
for(q=p->head;q&&q->link;q=q->link);// 特別注意
if(!q)
p->head=newg;
else
q->link=newg;
}
return hb;
}
void printpackingbox(GBOX *hbox) //輸出
{
GBOX *p;
GNODE *q;
int i=0;
for(p=hbox;p;p=p->next)
{
printf("這是第%d個箱子，里面有",++i);
for(q=p->head;q;q=q->link)
{
printf("編號為%d",q->gnum);
}
printf("
");
}
}
int main(int argc, char** argv){ //主函數
int n;
GOODS *goods;
GBOX *hbox;
printf("請你輸入物品的個數： ");
scanf("%d",&n);
goods=(GOODS *)malloc(n*sizeof(GOODS));
for(int i=0;i<n;i++){
printf("輸入第%d個物品的體積是",i+1);
scanf("%d",&goods[i].gv);
goods[i].go=i+1;
}
sortvolume(goods,n);
hbox=packingbox(goods,n); //箱子的頭結點
printpackingbox(hbox); //輸出
return 0;
}
3 示意圖
箱子掛上物品后就是這個模樣
4 分析代碼
現在有很多
排序方法，選擇，插入，快排，冒泡，歸并隨意寫1個就好。
這個程序有幾處特別好，不知道你們看沒有看出來，2個for語句循環里面是空的，for(p=hb;p&&p->reminder<goods[i].gv;p=p->next); 這個分號特別注意，不管我開不開新箱子，我總會用1個p指針來處理箱子的問題，而p停的地方就是當前這個物品1定可以放進去的，如果p為空。我就開新箱子放，如果p不為空，直接放進去。利用一樣的思路，我就只用1個q指針很好的處理了裝在箱子里面的物品鏈，不管頭不為空。q停下的地方1定可以把該物品掛在后面，for(q=p->head;q&&q->link;q=q->link);（分號特別注意）我利用了尾插法，有人會問為何不用頭插法，緣由是雖然這樣好處理，但是這樣物品就被倒著放在里面了。
這次我還知道了，盡量使for循環里面嵌套if else 不要在if else 里面嵌套for循環，由于1般是大時間復雜度嵌套小的。
5 運行結果
注意箱子設的最大體積是10，不可以超過10
如果里面有甚么毛病，或甚么建議，歡迎大家提出來
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
