fill_box.cpp

数据结构中的贪心法装箱问题

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct ele{
	int vno;
	struct ele *link;
}ELE;

typedef struct hnode{
	int remainder;
	ELE *head;
	struct hnode *next;
}HNODE;

void main(){
	int n, i, box_count, box_volume, *a;
	HNODE *box_h, *box_t, *u;
	ELE *p, *q;
	printf("输入箱子的容积：");
	scanf("%d",&box_volume);
	printf("输入物品种类：");
	scanf("%d",&n);
	a=(int *)malloc(sizeof(int)*n);
	printf("请按从大到小的顺序输入物品的体积：");
	for(i=0;i<n;i++)
		scanf("%d",a+i);
	box_h=box_t=NULL;
	box_count=0;
	for(i=0;i<n;i++){
		p=(ELE *)malloc(sizeof(ELE));
		p->vno=i;
		for(u=box_h; u!=NULL; u=u->next)
			if(u->remainder>=a[i]) break;
		if(u==NULL){
				u=(HNODE *)malloc(sizeof(HNODE));
				u->remainder=box_volume-a[i];
				u->head=NULL;
				if(box_h==NULL) box_h=box_t=u;
				else box_t=box_t->next=u;
				u->next=NULL;
				box_count++;
		}
		else u->remainder-=a[i];
		for(q=u->head;q!=NULL && q->link!=NULL;q=q->link);
			if(q==NULL){
				p->link=u->head;
				u->head=p;
			}
			else{
				p->link=u->head;
				u->head=p;
			}
	}
	printf("共使用%d只箱子，",box_count);
	printf("各箱子装物品情况如下：\n");
	printf("<number,weight>:\n ");
		for(u=box_h,i=1;u!=NULL;u=u->next,i++){
			printf("第%2d只箱子还剩余%4d，所装物品有：\n",i,u->remainder);
			for(p=u->head;p!=NULL;p=p->link)
				printf("<%-2d,%4d>\n",p->vno+1,a[p->vno]);
			printf("\n");
		}	
}