贪心法装箱算法 c++

浏览数：21 / 时间：2015年06月08日

//参考书上的算法
#include <iostream>
#define N 12
#define V 100
using 
namespace 
std;
 
typedef 
struct 
box{
int 
id;
int 
boxsize;
struct 
box* next;
}BOX;
 
void 
initboxlist(BOX ** H)
{
    *H=(BOX*)malloc(sizeof(BOX));
    (*H)->id=0;
    (*H)->boxsize=0;
    (*H)->next=NULL;
}
 
BOX* findbox(BOX* H,int 
vl,int 
v)
{
    BOX* p=H;
    while(p != NULL)
    {
        if(p->boxsize+vl<=v)
            break;
        p=p->next;
    }
    return 
p;
}
 
void 
addlisttail(BOX* H,BOX* p)
{
    BOX* q=H;
    BOX* tmp=H->next;
    while(tmp!=NULL)
    {
        q=tmp;
        tmp=tmp->next;
    }
    q->next=p;
}
 
void 
printlist(BOX* H)
{
    BOX* p=H;
    while(p!=NULL)
    {
        cout<<p->id+1<<" "<<p->boxsize<<endl;
        p=p->next;
    }
 
}
 
 
void 
addbox(int 
vol[],int 
v)
{
    BOX* H=NULL;
    int 
boxcount=0;
    initboxlist(&H);
 
 
    for(int 
i=0;i<N;i++)
    {
        BOX *p=findbox(H,vol[i],v);
        if(p==NULL)
        {
           BOX *t=(BOX*)malloc(sizeof(BOX));
            boxcount++;
            t->id=boxcount;
            t->boxsize=vol[i];
            t->next=NULL;
            addlisttail(H,t);
        }
        else
            p->boxsize+=vol[i];
    }
    printlist(H);
}
 
int 
main()
{
    int 
vol[]={60, 45, 35, 20, 20, 20,55,87,65,76,67,100};
    addbox(vol,V);
 
}