贪心算法解决背包问题
#include<stdio.h>
#include<stdlib.h>
void Sort(int n,float v[n+1],float w[n+1])//这里用的是选择排序
{
int b[n+1];
int i,j,k,t;
for(i=1;i<=n;i++)
b[i]=v[i]/w[i];
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(b[j]>b[i])
{
k=b[i];
b[i]=b[j];
b[j]=k;
t=j;
}
}
k=v[i];
v[i]=v[t];
v[t]=k;
k=w[i];
w[i]=w[t];
w[t]=k;
}
}
void Knapsack(int n,float M,float v[n+1],float w[n+1],float x[])
{
int i;
float c=M;//c为背包剩余容量
for(i=1;i<=n;i++)//x[]初始化
x[i]=0;
Sort(n,v,w);
//执行该函数以下语句的前提是数组v,w已根据单位重量价值从大到小排好序
for(i=1;i<=n;i++)
{
if(w[i]>c)//表明背包装不下完整的第i个物品
break;
x[i]=1;
c-=w[i];
}
if(i<=n)
x[i]=c/w[i];//分割物品
}
int main(int argc,char *argv[])
{
int n=3;
//可以用已赋值的变量定义数组的初始长度,但不可以初始化
float v[]={0,60,120,100};//存储物品价值
float w[]={0,10,30,20};//存储物品重量
float M=50;//背包容量
float x[3];//解向量
Knapsack(n,M,v,w,x);
printf("装入背包的物品为:");
int i;
for(i=1;i<=n;i++)
printf("%.2f ",x[i]);
return 0;
}