C语言版贪心算法背包问题

#include<>

#define N 100

typedef struct bao{

int num;

float w;

float v;

};

typedef struct avg{

int num;

(

float val;

float w;

float v;

};

struct bao b[N];

struct avg d[N];

int n;

float c;

^

void Sort()

{

int i,j,k;

struct avg temp[N];

for(i=0;i

{

k = i;

for(j=i+1;j

if(d[k].val

if(k != i)

【

{

temp[i]=d[i];

d[i]=d[k];

d[k]=temp[i];

}

}

}

float knapsack(){

int i;

】

float x[N],sum = 0;

for(i=0;i

for(i=0;i

if(d[i].w>c) break;

x[d[i].num] = 1;

sum += d[i].v;

c -= d[i].w;

}

if(i

x[d[i].num] = c/d[i].w;

:

sum += x[d[i].num] * d[i].v;

}

return sum;

}

int main(){

int i,j,k;

float sum;

printf("请输入物品总数：");

scanf("%d",&n);

,

printf("\n请输入背包容量：");

scanf("%f",&c);

printf("\n请输入各物品重量及价值（格式：xx,xx）：");

for(i=0;i

scanf("%f,%f",&b[i].w,&b[i].v);

}

for(i=0;i

for(i=0;i

d[i].val = b[i].v/b[i].w;

d[i].v = b[i].v;

d[i].w = b[i].w;

}

Sort();

sum = knapsack();

printf("%.2f\n",sum);

}