【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)


相关推荐

  • ssdp协议介绍_wsd协议

    ssdp协议介绍_wsd协议SSDP是一个“简单服务发现协议”,即英文“SimpleServiceDiscoveryProtocol的缩写”,该协议定义了如何在网络上发现网络服务的方法。SSDP也规定了存放在XML文件中的信息格式。SSDP信息的传送是依靠HTTPU和HTTPMU进行的。不论是控制点,或是UPnP设备,工作中都必然用到SSDP,设备接入网络之后,要利用它向网络广播自己的存在(广播的信息中还有设备位

    2022年10月11日
  • VirtualBox 主机ping不通虚拟机的解决办法

    VirtualBox 主机ping不通虚拟机的解决办法虚拟机与主机之间相互ping通有一个问题,就是虚拟机能够ping通主机本地主机ping不通虚拟机:解决办法:1、如果虚拟机有两个网卡将虚拟机网卡2的连接方式改成桥接即可:⚠️要将虚拟机重启,否则是成功不了的(重要)然后就能够通过网卡2进行连接:2、虚拟机只有一个网卡也是将网卡1改成桥接模式⚠️要将虚拟机重启,否则是成功不…

  • bootoption没有启动项_javacontinue的用法

    bootoption没有启动项_javacontinue的用法一、现象从fetch说起,用fetch构造一个POST请求。1fetch(‘http://127.0.0.1:8000/api/login’,{2method:”POST”,3headers:({4’Content-Type’:’application/x-www-form-urlencoded’5}),6body:”name=”+name…

    2022年10月30日
  • python画图[通俗易懂]

    python画图[通俗易懂]Matplotlibpython图形可以分为两部分。一个是外部的整体设置,比如坐标轴的设置,注释,透明度等;一个是内部具体图形,不同图形可能大同小异。外部设置,是我们需要掌握的内容。内部具体图形的操作,用的时候搜索下就好。

  • android visible invisible和gone差异

    android visible invisible和gone差异

  • 谷歌浏览器怎么安装crx插件_谷歌浏览器怎么安装crx插件

    谷歌浏览器怎么安装crx插件_谷歌浏览器怎么安装crx插件Chrome67版本(大概2018.06.06的更新包)开始,插件已经无法离线安装啦,也就是自己无法使用crx文件安装插件,而只能从chrome.google.com/webstore上安装。

发表回复

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

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