大家好，又见面了，我是你们的朋友全栈君。
1.题目描述：——背包问题
有若干物品，每种物品的价值和重量各不相同，将物品装入一个容量有限的背包，如何选择装入的物品，使背包的价值最大。
2.题目分析：
要是背包中的物品价值最大，则需要在有限的重量中尽可能装入价值更大的物品，基于这种思想则采取贪心算法
首先计算物品的单位价值，即价值/重量，根据单位价值对物品进行排序，优先装入单位价值高的物品，直至背包装满。
3.代码实现：
#include <stdio.h>
int n;//物品数量
double c;//背包容量
double v[999];//物品的价值
double w[999];//物品的重量
double cw = 0.0;//背包重量
double cp = 0.0;//背包价值
double bestp = 0.0;//当前最优价值
double perp[999];//物品性价比排序
int order[100];//物品编号
int put[100];//装入标识
void sort()
{
int i,j;
int temporder = 0;
double temp= 0.0;
for(i=1;i<=n;i++)
perp[i]=v[i]/w[i];
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
{
temp = perp[i];
perp[i]=perp[j];
perp[j]=temp;
temporder=order[i];
order[i]=order[j];
order[j]=temporder;
temp = v[i];
v[i]=v[j];
v[j]=temp;
temp=w[i];
w[i]=w[j];
w[j]=temp;
}
}
}
void backtrack(int i)
{
double bound(int i);
if(i>n)
{
bestp = cp;
return;
}
if(cw+w[i]<=c)
{
cw+=w[i];
cp+=v[i];
put[i]=1;
backtrack(i+1);
cw-=w[i];
cp-=v[i];
}
if(bound(i+1)>bestp)
backtrack(i+1);
}
double bound(int i)
{
double leftw= c-cw;
double b =cp;
while(i<=n&&w[i]<=leftw)
{
leftw-=w[i];
b+=v[i];
i++;
}
if(i<=n)
b+=v[i]/w[i]*leftw;
return b;
}
int main()
{
int i;
printf("请输入物品的数量和容量：");
scanf("%d%lf",&n,&c);
for(i=1;i<=n;i++)
{
printf("第%d个物品的重量和价值：",i);
scanf("%lf %lf",&w[i],&v[i]);
order[i]=i;
}
sort();
backtrack(1);
printf("最大价值为：%lf\n",bestp);
printf("装入的物品次序为：");
for(i=1;i<=n;i++)
{
if(put[i]==1)
printf("%d ",order[i]);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/159137.html原文链接：https://javaforall.net
