c语言背包问题

c语言背包问题

算法分析：
使用贪心策略求解此类问题时，首先要选出最优的度量标准。
可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。
显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。最优的度量标准是单位价值。
背包问题算法思路：
1、将各个物品按照单位价值由高到低排序；
2、取价值最高者放入背包；
3、计算背包的剩余空间；
4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。
#include

void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);

int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已经按照单位价值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");

}


void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}

for(i=0;i{
if(w[i] > c)
{
break;
}

x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}

if(i<=n)//还可以放入一个物品的一部分
{
x[i] = c/w[i];

printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);
}
}


void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}

for(i=0;i{
if(w[i] > c)
{
break;
}

x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}

#include
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已经按照单位价值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}

void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}

for(i=0;i{
if(w[i] > c)
{
break;
}

x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}

if(i<=n)//还可以放入一个物品的一部分
{
x[i] = c/w[i];

printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);
}
}

void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}

for(i=0;i{
if(w[i] > c)
{
break;
}

x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}