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
如果里面有甚么毛病，或甚么建议，欢迎大家提出来