【C语言】——背包问题详解「建议收藏」

【C语言】——背包问题详解「建议收藏」1.题目描述:——背包问题有若干物品,每种物品的价值和重量各不相同,将物品装入一个容量有限的背包,如何选择装入的物品,使背包的价值最大。2.题目分析:要是背包中的物品价值最大,则需要在有限的重量中尽可能装入价值更大的物品,基于这种思想则采取贪心算法首先计算物品的单位价值,即价值/重量,根据单位价值对物品进行排序,优先装入单位价值高的物品,直至背包装满。3.代码实现:#include<stdio.h>intn;//物品数量doublec;//背包容量…

大家好,又见面了,我是你们的朋友全栈君。

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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号