贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。
应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。
2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。
程序1
#include <iostream.h>
struct goodinfo
{
float p; //物品效益
float w; //物品重量
float X; //物品该放的数量
int flag; //物品编号
};//物品信息结构体 void Insertionsort(goodinfo goods[],int n)
{
int j,i;
for(j=;j<=n;j++)
{
goods[]=goods[j];
i=j-; while (goods[].p>goods[i].p)
{
goods[i+]=goods[i];
i--;
}
goods[i+]=goods[];
}
}//按物品效益，重量比值做升序排列 void bag(goodinfo goods[],float M,int n)
{ float cu;
int i,j;
for(i=;i<=n;i++)
goods[i].X=;
cu=M; //背包剩余容量
for(i=;i<n;i++)
{
if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
break; goods[i].X=;
cu=cu-goods[i].w;//确定背包新的剩余容量
}
if(i<=n)
goods[i].X=cu/goods[i].w;//该物品所要放的量
/*按物品编号做降序排列*/
for(j=;j<=n;j++)
{
goods[]=goods[j];
i=j-; while (goods[].flag<goods[i].flag)
{
goods[i+]=goods[i];
i--;
}
goods[i+]=goods[];
}
///////////////////////////////////////////
cout<<"最优解为:"<<endl;
for(i=;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
} void main()
{
cout<<"|--------运用贪心法解背包问题---------|"<<endl;
cout<<"|---power by zhanjiantao(028054115)---|"<<endl;
cout<<"|-------------------------------------|"<<endl;
int j;
int n;
float M;
goodinfo *goods;//定义一个指针
while(j)
{
cout<<"请输入物品的总数量：";
cin>>n;
goods=new struct goodinfo [n+];//
cout<<"请输入背包的最大容量：";
cin>>M;
cout<<endl;
int i;
for(i=;i<=n;i++)
{ goods[i].flag=i;
cout<<"请输入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"请输入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
cout<<endl; } Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press <1> to run agian"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
}
}
程序2
#include<stdio.h>
#include<stdlib.h>
#define Max 100/*定义栈结构*/
typedef struct list{ int data[Max]; int top;}
Seqstack; /*定义一个用来存储结果的链表*/
typedef struct List{ Seqstack result; struct List * Next;}
Seqlist,*Pointer;
void Inicial_List(Pointer p)
{ p=(Pointer)malloc(sizeof(Seqlist));
p->Next=NULL;}
Seqstack Push_Stack(int n,Seqstack s)
{ s.top++;
s.data[s.top]=n;
return s;}
int Add_Stack(Seqstack s)
{
Int total=,i;
if(s.top>=)
{ for(i=;i<=s.top;i++)
total+=s.data[i];
}
else
{ total=; }
return total;}
Seqstack Pop_Stack(Seqstack s)
{
printf("%d",s.data[s.top]);
if(s.top>=)
s.top--;
return s;}/*执行回溯操作的函数*//*参数说明：n->数的总的个数，a[]用来存放数的数组,k查找的总体积*/
Pointer Query_Result(int n,int b[],int k)
{ int i,j;
Seqstack mystack;
Seqlist *newnode;
Pointer r,p=NULL;
Inicial_List(p);
r=p; for(i=;i<n;i++)
{ mystack.top=-;
j=i;
while(j<n)
{
if(Add_Stack(mystack)+b[j]<k)
{ mystack=Push_Stack(b[j],mystack);
j++; }
else if(Add_Stack(mystack)+b[j]==k)
{ mystack=Push_Stack(b[j],mystack);
newnode=(Pointer)malloc(sizeof(Seqlist));
newnode->result=mystack;
newnode->Next=NULL;
r->Next=newnode;
r=newnode;
mystack=Pop_Stack(mystack);
j++;
}
else if(Add_Stack(mystack)+b[j]>k)
{
j++;
}
}
}
return p;
}
void Print_List(Pointer p)
{
int i,j=;
p=p->Next;
printf("welcome the outer\n");
if(p==NULL)
printf("there no results\n");
while(p!=NULL)
{
j++;
printf("the %d result is: ",j);
for(i=;i<=p->result.top;i++)
{ printf(" %d",p->result.data[i]);
}
p=p->Next;
printf("\n"); }
printf("\n");}
void Sort_Array(int b[],int n)
{
int i,j,temp;
for(i=;i<n;i++)
{ for(j=;j<n-i;j++)
{ if(b[j]<b[j+])
{ temp=b[j];
b[j]=b[j+];
b[j+]=temp;
}
}
}
}
void main()
{
int i,n,k,select,a[Max];
Pointer head;
printf("******************************************\n"); printf("1 start\n2 exit\n");
scanf("%d",&select);
while(select==)
{
printf("please input the total products\n");
scanf("%d",&n);
printf("please input the volumn of n products\n");
for(i=;i<n;i++)
{
printf("please input the %d integers",i+);
scanf("%d",&a[i]);
}
printf("\n");
printf("please input the volunm to put\n");
scanf("%d",&k);
Sort_Array(a,n);
head=Query_Result(n,a,k);
Print_List(head);
printf("******************************************\n");
printf("1 start\n2 exit\n"); scanf("%d",&select);
}
}
程序3
#include<stdio.h>
#include<stdlib.h>
#define Max 100
/*定义栈结构*/
typedef struct list{ int data[Max]; int top;}Seqstack;
/*定义一个用来存储结果的链表*/
typedef struct List
{
Seqstack result;
struct List * Next;
}
Seqlist,*Pointer;
void Inicial_List(Pointer p)
{
p=(Pointer)malloc(sizeof(Seqlist));
p->Next=NULL;
}
Seqstack Push_Stack(int n,Seqstack s)
{ s.top++;
s.data[s.top]=n;
return s;
}
int Add_Stack(Seqstack s)
{ int total=,i;
if(s.top>=)
{
for(i=;i<=s.top;i++)
total+=s.data[i];
}
else
{
total=;
}
return total;
}
Seqstack Pop_Stack(Seqstack s)
{
printf("%d",s.data[s.top]);
if(s.top>=)
s.top--; return s;}
/*执行回溯操作的函数*//*参数说明：n->数的总的个数，a[]用来存放数的数组,k查找的总体积*/
Pointer Query_Result(int n,int b[],int k)
{
int i,j;
Seqstack mystack;
Seqlist *newnode;
Pointer r,p=NULL;
Inicial_List(p);
r=p;
for(i=;i<n;i++)
{
mystack.top=-;
j=i;
while(j<n)
{
if(Add_Stack(mystack)+b[j]<k)
{
mystack=Push_Stack(b[j],mystack);
j++;
}
else if(Add_Stack(mystack)+b[j]==k)
{
mystack=Push_Stack(b[j],mystack);
newnode=(Pointer)malloc(sizeof(Seqlist));
newnode->result=mystack;
newnode->Next=NULL;
r->Next=newnode;
r=newnode;
mystack=Pop_Stack(mystack);
j++;
}
else if(Add_Stack(mystack)+b[j]>k)
{
j++;
}
}
}
return p;
}
void Print_List(Pointer p)
{
int i,j=;
p=p->Next;
printf("welcome the outer\n");
if(p==NULL)
printf("there no results\n");
while(p!=NULL)
{
j++;
printf("the %d result is: ",j);
for(i=;i<=p->result.top;i++)
{
printf(" %d",p->result.data[i]);
}
p=p->Next;
printf("\n");
}
printf("\n");
}
void Sort_Array(int b[],int n)
{
int i,j,temp;
for(i=;i<n;i++) { for(j=;j<n-i;j++)
{
if(b[j]<b[j+])
{
temp=b[j];
b[j]=b[j+];
b[j+]=temp;
}
}
}
}
void main()
{
int i,n,k,select,a[Max]; Pointer head;
printf("******************************************\n");
printf("1 start\n2 exit\n"); scanf("%d",&select);
while(select==)
{
printf("please input the total products\n");
scanf("%d",&n);
printf("please input the volumn of n products\n");
for(i=;i<n;i++)
{
printf("please input the %d integers",i+);
scanf("%d",&a[i]); } printf("\n");
printf("please input the volunm to put\n");
scanf("%d",&k); Sort_Array(a,n);
head=Query_Result(n,a,k);
Print_List(head);
printf("******************************************\n");
printf("1 start\n2 exit\n");
scanf("%d",&select);
}
}