博客

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

核心代码

```c
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>
void Sort(int n, float v[],float w[])
{   float t[100];
float a,b,c;
for(int i=1;i<=n;i++)
t[i]=v[i]/w[i];
for(int k=1;k<=n;k++)
for(int j=k+1;j<=n;j++)
{
	if(t[k]<t[j])
	{
		a=t[k];
		t[k]=t[j];
		t[j]=a;
		b=w[k];
		w[k]=w[j];
		w[j]=b;
		c=v[k];
		v[k]=v[j];
		v[j]=c;
	}
}
}
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];//最后一个物品运行部分转入
}
void main()
{    int n,i;
float m;
float v[100],w[100],x[100];
printf("输入物品数目和背包容量：");
scanf("%d %f",&n,&m);
printf("输入物品价值:\n");
for(i=1;i<=n;i++)
{  
	scanf("%f",&v[i]);
}
printf("输入物品重量:\n");
for(i=1;i<=n;i++)
{  
	scanf("%f",&w[i]);
}
Knapsack(n,m,v,w,x);
for(i=1;i<=n;i++)
printf("价值%f重%f的物品占比：%f\n",v[i],w[i],x[i]);
}