背包问题:小偷偷东西问题

题目描述

小偷来到了一个神秘的王宫,突然眼前一亮,发现5个宝贝,每个宝贝的价值都不一样,且重量也不一样,但是小偷的背包携带重量有限,所以他不得不在宝贝中做出选择,才能使偷到的财富最大,请你帮助小偷计算一下。

输入描述:

宝贝价值:6,3,5,4,6
宝贝重量:2,2,6,5,4
小偷背包容量:10

输出描述:

偷到宝贝的总价值:15

示例1

输入

6,3,5,4,6

2,2,6,5,4

10

输出

15

#华为#
全部评论
#include <stdio.h> #define BIT(n) (1<<n) int main() {     int v[5];//价值   int h[5];//重量     int c=0;//最大容量     unsigned char bit=31;//二进制11111 分别代表5个宝贝 ,选中为1,未选中为0 共有2^5种 可能性     int maxv=0;//偷到宝贝的总价值     scanf("%d,%d,%d,%d,%d",&v[0],&v[1],&v[2],&v[3],&v[4]);     scanf("%d,%d,%d,%d,%d",&h[0],&h[1],&h[2],&h[3],&h[4]);     scanf("%d",&c);     //循环32次     for(int i=0;i<=bit;i++)     {//判断选中宝贝重量之和是否小于最大容量      if(h[0]*(i&BIT(0))+h[1]*((i&BIT(1))>>1)+h[2]*((i&BIT(2))>>2)+h[3]*\   ((i&BIT(3))>>3)+h[4]*((i&BIT(4))>>4)<=c)      {   //选中宝贝价值是否大于之前的总价值          if( v[0]*(i&BIT(0))+v[1]*((i&BIT(1))>>1)+v[2]*((i&BIT(2))>>2)+v[3]*\ ((i&BIT(3))>>3)+v[4]*((i&BIT(4))>>4)>maxv)          maxv=v[0]*(i&BIT(0))+v[1]*((i&BIT(1))>>1)+v[2]*((i&BIT(2))>>2)+v[3]*\ ((i&BIT(3))>>3)+v[4]*((i&BIT(4))>>4);      }     }                 printf("\n%d\n",maxv);     return 0; } //自己用C语言写的,格式有点乱,凑合着看吧,命令行输入的逗号是英文的逗号,别弄错了 //"\"是我为了看着简洁加上的,不能运行的话删掉就行了
2 回复 分享
发布于 2018-08-08 22:21
也抽到考这题目了,可惜的是当时有人找,点保存,保存不了,就误点了提交,无法再考了,造成机考失败。 我觉得思路如下可行,并且简单。 1、既然是拿最大价值,就把价值数组从大到小排序,同时要把价值对应的重量也要对应上。排序后对应的如图 2、按价值循环加,加的同时判断对应的重量是否大于10,如果不是就继续加 3、最终算出最大价值和对应的重量
1 回复 分享
发布于 2020-02-18 21:03
昨晚的机试题,不太懂动态规划,第一反应可以算价值/重量的性价比然后降序排序,再循环,判断后输出满足容量的最大价值;第二反应是只有5个宝贝,直接穷举所有可能的选择,循环判断满足容量的最大价值;用了第二种,但可能因为是读输入的没读对的问题(输入是三行,每个值之间逗号隔开),没有通过,有点难受。
点赞 回复 分享
发布于 2019-07-29 12:15
不错不错
点赞 回复 分享
发布于 2019-02-15 17:04
01背包
点赞 回复 分享
发布于 2018-08-08 23:32
case通过率60%,实在想不出还有什么情况……
点赞 回复 分享
发布于 2018-08-08 21:30
有个问题,用c++如何把逗号分隔的数据读成数组?
点赞 回复 分享
发布于 2018-08-08 21:27
今晚华为笔试?
点赞 回复 分享
发布于 2018-08-08 21:26
为啥我的输入不是三行!
点赞 回复 分享
发布于 2018-08-08 21:19

相关推荐

2025-12-12 19:01
南京航空航天大学 C++
秋招没咋投,准备&nbsp;wxg&nbsp;转正之后摆烂了。结果不堪字节&nbsp;HR&nbsp;的骚扰还是面了一下字节。之前想去字节的时候怎么面都挂。现在想着随便面一下结果三面技术面都意外顺利还有加面。十月中旬字节发了意向,wxg&nbsp;转正结果无响应。十月底字节拉了保温群,wxg&nbsp;口头通过,系统显示考核中。十一月初和字节&nbsp;ld&nbsp;交流之后得知&nbsp;base&nbsp;居然能选海外,甚至能小&nbsp;wlb&nbsp;一下,wxg&nbsp;无响应无人联系。十一月中旬把字节&nbsp;base&nbsp;转到了海外,wxg&nbsp;流程灰了,一问超时忘处理了,过两天又变考核中了。十一月下旬字节换了海外&nbsp;HR&nbsp;对接,问了期望薪资,wxg&nbsp;考核终于显示通过,无&nbsp;HR&nbsp;保温,无其他保温。十一月底给字节报了个天价,想吓吓他们,同时告诉微信字节要开了,微信无响应。同样十一月底字节&nbsp;HR&nbsp;告诉我确实给不到那么高,但是能拿期权补上,问能不能接受。微信无响应。同样十一月底字节&nbsp;HR&nbsp;告知了具体方案,符合预期。&nbsp;微信无响应。十二月上旬催&nbsp;wxg&nbsp;不开我就盲拒了,wxg&nbsp;HR&nbsp;火急火燎的打电话问情况,问期望。我给了一个不算夸张的总包数字,因为今年市场在涨,过了三天还不联系我,我再催,约时间下午打电话,非得在我给出的数字上压下去几万,微信又不差这点,为什么不能满足我,让我没有拒绝的理由呢?一番纠结抗争,求稳还是追求挑战,最终选择接受迎接新的挑战,因为堂吉诃德永远不会停下脚步!回想起来,在&nbsp;wxg&nbsp;谈薪的阶段,我认为并没有给予我一定的重视,即使&nbsp;HR&nbsp;表示我在实习期间的表现和之前的面评都很靠前。也没有感觉到想要争取我,虽然我表示拒了&nbsp;offer&nbsp;之后要给我加面委定&nbsp;t6&nbsp;再涨,但我三个月没面试让我面面委那就是白给,还是算了。有缘再见了我亲爱的&nbsp;wxg,再见了曾经的梦中情厂,再见亲爱的&nbsp;mt,再见亲爱的朋友们。也再见,北京的一切。我想润了。秋招结束,卸载牛客,下一个三年,下一个五年,下一个十年后再来看看。
面试中的大熊猫爱吃薯...:我嫉妒得狗眼通红
点赞 评论 收藏
分享
评论
点赞
23
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务