大家好,又见面了,我是你们的朋友全栈君。
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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159137.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...