发布时间 : 星期四 文章c语言经典算法设计方法更新完毕开始阅读57fff9ad66ec102de2bd960590c69ec3d4bbdb6d
上述算法能求出需要的箱子数box_count，并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解，设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需三只箱子，各箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
【程序】
#include stdio.h
#include stdlib.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,*j； ELE*p,*q；
Printf(\输入箱子容积\\n\； Scanf(\； Printf(\输入物品种数\\n\； Scanf(\；
a=(int*)malloc(sizeof(int)*n)；
printf(\请按体积从大到小顺序输入各物品的体积：\； for(i=0；i n；i++) scanf(\； box_h=box_t=NULL； box_count=0； for(i=0；i n；i++) {
p=(ELE*)malloc(sizeof(ELE))； p-vno=i；
for(j=box_h；j！=NULL；j=j-next) if(j-remainder=a[i]) break； if(j==NULL) {
j=(HNODE*)malloc(sizeof(HNODE))； j-remainder=box_volume-a[i]； j-head=NULL； if(box_h==NULL) box_h=box_t=j；
else box_t=box_t-next=j； j-next=NULL； box_count++； }
else j-remainder-=a[i]；
for(q=j-next；q！=NULL&&q-link！=NULL；q=q-link)； if(q==NULL) {
p-link=j-head；
j-head=p； } else {
p-link=NULL； q-link=p； } }
printf(\共使用了%d只箱子\，box_count)； printf(\各箱子装物品情况如下：\； for(j=box_h,i=1；j！=NULL；j=j-next,i++) {
printf(\第-只箱子，还剩余容积M，所装物品有；\\n\； for(p=j-head；p！=NULL；p=p-link) printf(\； printf(\； } } }