从问题的某一个初始解开始，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可以看出，贪心算法存在以下3个问题：
(1)不能保证最后的解是最优的。
(2)不能用来求最大或最小解问题。
(3)只能求满足某些约束条件的可行解的范围。
贪心算法的基本思路如下：
(1)建立数学建模来描述问题。
(2)把求解的问题分成若干个问题。
(3)对每一子问题求解，得到子问题的局部最优解。
(4)把子问题的局部最优解合成原来问题的一个解。
实现该算法的过程如下：
(1)从问题的某一初始解出发。
(2)while能向给定总目标前进一步。
(3)求出可行解的一个解元素。
(4)由所有解元素组合问题的一个可行解。
装箱问题
设由编号为0,1,......,n-1的n种物品，体积分别为v0,v1,....,vn-1。将这n种物品装到容量都为V的若干箱子里。约定这种n种物品的体积均不超过V，即对于0<=i 算法思想： 如果将n种物品的集合分解为n个或小于n个物品的所有子集，我们使用最优解法就可以找到。但是所有可能的划分的总数会显得很大，对于比较大的n，如果要找出所有可能的划分，会需要花费很多时间。此时可以使用贪心算法这种近似算法来解决装箱问题。 该算法依次将物品放到它第一个能放进的箱子种，该算法虽然不能暴走找到最优解，但还是能找到最优解的近似解。设n件物品的体积是按从大到小排好序的，即有v0>=v1>=.....>=vn-1。如果不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序对物品重新编号即可。这个就是一个典型的贪心算法问题：
先取体积最大的
{ 输入箱子的容积;
输入物品种类n;
按体积从到到小顺序，输入各物品的体积;
预置已用箱子链为空;
预置已用箱子计数器box_count为0;
for(i=0;i
{ 从已用的第一只箱子开始顺序寻找能放入物品i的箱子j;
if(已用箱子都不能再存放物品 i)
{ 另用一个箱子，并将物品i放入该箱子;
box_count++;
}
else
将物品i放入箱子j;
}
}
通过上述算法，能够求出需要的箱子数box_count，并能求出各箱子所装物品 。
再看下面的例子。
设有6种物品，他们的体积分别为：60，45，35，20，20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需3个箱子，各箱子所装物品为:第一只箱子装物品 1，3;第二只箱子装物品2,4,5;第三只箱子装物品6。而最优解分为两只箱子，分别装物品1,4,5 和2,3,6。
#include
#include
#define N 6
#define V 100
typedef struct box
{
int no;
int size;
struct box* next;
}BOX;
void init_list(BOX** H)
{
*H=(BOX*)malloc(sizeof(BOX));
(*H)->no=0;
(*H)->size=0;
(*H)->next=NULL;
}
BOX* find_p(BOX* H,int volume,int v)
{
BOX* p=H->next;
while(p!=NULL){
if(p->size+volume<=v){ break; } p=p->next;
}
return p;
}
void add_list_tail(BOX* H,BOX* p)
{
BOX* tmp=H->next;
BOX* q=H;
while(tmp!=NULL){
q=tmp;
tmp=tmp->next;
}
q->next=p;
}
void print_list(BOX* H)
{
BOX* p=H->next;
while(p!=NULL){
printf("%d:%d\n",p->no,p->size;
p=p->next;
}
}
int add_box(int volume[],int v)
{
int count=0;
int i;
BOX* H=NULL;
init_list(&H);
for(i=0;i
BOX* p=find_p(H,volume[i],v);
if(p==NULL){
count++;
p=(BOX*)malloc(sizeof(BOX));
p->no=count;
p->size=volume[i];
p->next=NULL;
add_list_tail(H,p);
}
else{
p->size+=volume[i];
}
}
print_list(H);
return count;
}
void main()
{
int ret;
int volumes[]={60,45,35,20,20,20};
ret=add_box(volumes,V);
printf("%d\n",ret);
}
找零方案
编写一段程序实现超市找零方案，只需输入需要补给顾客的金额，然后通过程序计算该金额可以由哪些面额的人民币组成。
算法思想：
人民币由100，50，10，20，5，1，0.5，0.1等多种面额(单位为元)。再找零钱时可以由多种方案，例如需补零钱68.90元，至少可以有以下3种方案：
1张50，1张10，一张5，3张1，1张0.5，4张0.1;
2张20，2张10，1张5，3张1，1张0.5，4张0.1;
6张10，1张5，3张1，1张0.5，4张0.1.
#include
#define MAXN 9
int pravalue[MAXN]={10000,5000,1000,500,100,50,10};
int num[MAXN]={0};
int exchange(int n)
{
int i;
for(i=0;i
if(n>pravalue[i]){ //找到比n小的最大面额
break;
}
}
while(n>0&&i
if(n>=pravalue[i]){
n-=pravalue[i];
num[i]++;
}
else if(n<10&&n>=5){
num[MAXN-1]++;
break;
}
else{
i++;
}
}
return 0;
}
void main()
{
int i;
float m;
printf("请输入找零的金额：");
scanf("%f",&m);
exchange((int)100*m);
printf("\n%.2f元零钱的组成：\n",m);
for(i=0;i
if(num[i]>0){
printf("%6.2f:%d张\n",(float)pravalue[i]/100.0,num[i]);
}
}
}