贪婪算法
贪婪算法
改进的背包问题：给定一个超递增序列和一个背包的容量，然后在超递增序列中选（只能选一次）或不选
每一个数值，使得选中的数值的和正好等于背包的容量。
代码思路：从最大的元素开始遍历超递增序列中的每个元素，若背包还有大于或等于当前元素值的空间，
则放入，然后继续判断下一个元素；若背包剩余空间小于当前元素值，则判断下一个元素
简单模拟如下：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{/*产生超递增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array=t+random(k)+1;
}
}
void output(long array[],int n)
{/*输出当前的超递增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array);
}
}
void beibao(long array[],int cankao[],long value,int count)
{/*背包问题求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍历超递增序列中的每个元素*/
{
if(r>=array)/*如果当前元素还可以放入背包，即背包剩余空间还大于当前元素*/
{
r=r-array;
cankao=1;
}
else/*背包剩余空间小于当前元素值*/
cankao=0;
}
}
void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已经选中的元素之和*/
if(cankao==1)
value1+=array;
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
贪婪算法的另一种写法，beibao函数是以前的代码，用来比较两种算法：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array);
}
}
void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array)
{
r=r-array;
cankao=1;
}
else
cankao=0;
}
}
int beibao1(long array[],int cankao[],long value,int n)
{/*贪婪算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物体，再考虑小的物体*/
if((value1+array)<=value)/*如果当前物体可以放入*/
{
cankao=1;/*1表示放入*/
value1+=array;/*背包剩余容量减少*/
}
else
cankao=0;
if(value1==value)
return 1;
return 0;
}
void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao==1)
value1+=array;
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
