贪心算法--背包问题
1. 背包问题
给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? (说明,以下算法与教材147页给出的算法思想是一样的,教材上的算法事先对物品信息进行了排序)
void Knapsack(int n,float M,float v[],float w[],float x[])
{
Sort(n,v,w);
int i;
for (i=1;i<=n;i++) x[i]=0;
float c=M;
for (i=1;i<=n;i++) {
if (w[i]>c) break;
x[i]=1;
c-=w[i];
}
if (i<=n) x[i]=c/w[i];//最后一个物品选择部分装入
}
具体代码:
#include<stdio.h>
float Knapsack(float *w,float *v,float *x,float c,int n)
{
int i,j,l;
float temp,sum=0;
float *a=new float[n];
for(i=0;i<n;i++)a[i]=v[i]/w[i];
printf("\n");
printf("以下分别是物品的重量、价值、价值/重量: \n");
for(i=0;i<n;i++)
{
printf("%f\t%f\t%f\t",w[i],v[i],a[i]);
printf("\n");
}
for(i=0;i<n-1;i++)
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
temp=v[j];
v[j]=v[j+1];
v[j+1]=temp;
}
}
printf("\n");
printf("以下根据价值/重量从低到高排序的w[] v[] a[] : \n");
for(i=0;i<n;i++)printf("%f %f %f\n",w[i],v[i],a[i]);
printf("\n");
for(l=n-1;l>=0;l--)
{
if(w[l]<=c)
{
x[l]=1;
sum=sum+v[l];
c=c-w[l];
}
else break;
}
x[l]=c/w[l];
sum=sum+x[l]*v[l];
delete []a;
printf("排序后的物品分别装入入背包多少:\n");
for(i=0;i<n;i++)
printf("%f ",x[i]);
printf("\n\n");
printf("背包装东西后最大总价值为:%f\n",sum);
printf("\n");
return sum;
}
void main()
{
int n,i;
float c;
printf("背包的重量为: ");
scanf("%f",&c);
printf("\n");
printf("一共有n个物品,n的值为: ");
scanf("%d",&n);
printf("\n");
float *w=new float[n];
float *v=new float[n];
float *x=new float[n];
printf("请分别输入物品的重量、价值(列如物品一:20 60(换行输入物品二)):\n");
for(i=0;i<n;i++)
{
scanf("%f %f",&w[i],&v[i]);
}
Knapsack(w,v,x,c,n);
delete []w;
delete []v;
delete []x;
}
结果截图: