贪心算法解装箱问题

问题描述

有N个物品，其重量大小为W,其取值范围为0<W<=V,有一批容量为V的箱子，问最少需要多少个箱子可以把这些物品装上。

思路

利用回溯和减枝是肯定可以的，毕竟是一种穷举。也可以利用动态规划方法来解决。本题主要讨论贪心算法的解决方法，其主要思想是每次选择都选择最优的，即让箱子每次都装能让箱子承受的住的最大重量，若遍历所有物品都没有能让箱子承受的住的，则换下一个箱子来装。其主要思想就跟有一张整的纸币，要将其换成10元，5元，1元的纸币，要求是换出的纸币的数量最少一样，那肯定是先从面值大的纸币换，换不了了再从面值次之的去换以此下去。
eg:

比如有5个物品其重量分别是 40 50 50 60 70 箱子的最大容量为100
则第一个箱子首先选择70，由于再没有其它的物品能供它装，换第二个箱子
第二个箱子首先装60，遍历后的最优为40,所以再装40，此时箱子的容量已满
换下一个箱子，第三个箱子首先选择50，然后遍历的最优为50
此时物品也已选择完，结束。所以所选择的最少箱子数量为三个。（ps:每个物品被选择后不再遍历它)

代码如下

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define V 100	//允许箱子能装的最大容积
#define N 5	//物体的数量

typedef struct {
	int number;//物体编号
	int volume;//物体容积
	_Bool flag1;//表示物品是否被装入
}object;

typedef struct{
	int memory[N];//装了啥物品,最多装N个
	int installed_capacity;//已装容量之和
	int surplus_capacity;//剩余容量
	_Bool flag;//标志表示该物品是否被用
}box;
//void mysort(object a[],int N);
void init(box*b){ //初始化函数
	b->flag=false;
	b->installed_capacity=0;
	b->surplus_capacity=V;
	int i;
	for(i=0;i<N;i++){
		b->memory[i]=0;
	}
}
void init_(object*b){//初始化函数，初始化箱子
	b->flag1=true;
	b->number=0;
	b->volume=0;
}
void mysort(object a[]){//排序，利用选择排序，有空写个快速排序
	int i,j;
	for(i=1;i<=N-1;i++){
		for(j=i;j<=N;j++){
			if(a[i].volume<a[j].volume){
				int temp1=a[j].number;
				int temp2=a[j].volume;
				a[j].number=a[i].number;
				a[j].volume=a[i].volume;
				a[i].number=temp1;
				a[i].volume=temp2;
			}
		}
	}
}
void myqsort(object a[],int begin ,int end){//快速排序方法
        if(begin<end){
            int key=a[begin].volume;
            int keynumber=a[begin].number;
            int i=begin;
            int j=end;
            while(i<j){
                while(i<j&&a[j].volume<key){
                    j--;
                }
                if(i<j){
                    a[i].number=a[j].number;
                    a[i].volume=a[j].volume;
                    i++;
                }
                while(i<j&&a[i].volume>key){
                    i++;
                }
                if(i<j){
                    a[j].number=a[i].number;
                    a[j].volume=a[i].volume;
                }
            }
            a[i].volume=key;
            a[i].number=keynumber;
            myqsort(a,begin,i-1);
            myqsort(a,i+1,end);
        }
}
int main(void){
	object *o=(object*)malloc(sizeof(object)*(N+1));
	int i;
    printf("请分别输入这%d物品的编号和重量：\n",N);
	for(i=1;i<=N;i++){
		//o[N].number=i;
		init_(&o[i]);
		scanf("%d%d",&((&o[i])->number),&((&o[i])->volume));//输入各物品的编号和容量
		(&o[i])->flag1=true;//此时表示此物品并未被使用
	}
	//box b[N];//利用realloc估计更好
    box*b=NULL;
	/*for(i=0;i<N;i++){
		init(&b[i]);
	}*/
	//mysort(o);
    myqsort(o,1,N);//快速排序。非递增排序
	int count=N;
	int num=0;//箱子数量
	int j;
	while(count){
        num++;
        b=(box*)realloc(b,sizeof(box)*num);
        init(&b[num-1]);
        int k=0;
		for(j=1;j<=N;j++){
			if(o[j].flag1==true&&b[num-1].surplus_capacity>=o[j].volume){
				b[num-1].installed_capacity+=o[j].volume;
				b[num-1].surplus_capacity-=o[j].volume;
				o[j].flag1=false;
				b[num-1].flag=true;
				b[num-1].memory[k++]=o[j].number;
				count--;//箱子被选就减一
			}
		}
	}
	printf("所用的箱子数量为%d\n",num);
    for(int i=0;i<num;i++){
        printf("第%d只箱子所装的物品编号为：\n",i+1);
        for(int j=0;j<N;j++){
            if(b[i].memory[j]==0){
                break;
            }
            printf("%d ",b[i].memory[j]);
            
        }
        printf("\n");
    }
    free(b);//当用完之后记得释放内存
    free(o);
    getchar();
    getchar();
	return 0;
    

	
}

其结果如下：

后言

很显然的是，利用贪心算法并不能总是得到最优解。相比较之下利用回溯和动态规划可以真正得到最优解。但其时间复杂度也必然会大大增加。(ps:有时间试试出一篇回溯或者动态规划的题解）
以上
end