问答题
有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？
发布日期：2020-12-11
试题解析
背包问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪，早期的作品可追溯到1897年数学家托比亚斯·丹齐格（Tobias Dantzig，1884-1956）的早期作品，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
- 中文名
- 背包问题
- 应用领域
- 运筹学，应用数学，密码学等
- 外文名
- Knapsack Problem
- 提出者
- Merkle-Hellman
物品
物品，汉语词语，读音为wù pǐn，是生产、办公、生活领域常用的一个概念，泛指各种东西或零星的物品，也泛指经济活动中涉及到实体流动的物质资料。
- 中文名
- 物品
- 拼音
- wù pǐn
- 出处
- 《通典·食货九》
- 外文名
- article、goods
- 释义
- 东西，物件
- 基本含义
- 生产办公生活领域常用的一个概念
重量
重量是物体受重力的大小的度量，重量和质量不同，单位是牛顿。它是一种物体的基本属性。在地球引力下，质量为1公斤的物质的重量为9.8牛顿。
- 中文名
- 重量
- 拼音
- zhòng liàng
- 外文名
- weight
- 出处
- 《花边文学·读书忌》
标签： 01 4,8,15,1,6,3 5,3,2,10,4,8 载重量 01
题王网让考试变得更简单
扫码关注题王，更多免费功能准备上线！
此试题出现在
古希腊建筑——（）、（）和（）
长期应用地西泮可产生耐受性，其特点是（ ）
现代化支付系统的参与主体包括（）。
关于农产品比价的说法，正确的有（ ）。
工程量清单是在19世纪30年代产生的
如何进行经济林优树选择？
垂体危象处理禁用（）。
一个完整的文化市场营销信息体系应包括内部信息系统、营销情报系统和（）。
（）贸易竞争的手段主要是价格竞争的品质竞争。
下列不属于“浙江三雕”的是（）。
暂无相关推荐~
有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为...
有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价...
在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算...
解0-1规划：
写出sys=zpk（{[]；[23]}，{1；[0-1]}，[-5；1]）的运行结果。
解0-1规划：
患女，30岁，1-0-0-1。外阴道有肿物脱出半年，屏气后妇科检查发现宫颈脱出于阴道外口，宫颈长度约4cm，伴有阴道前、后壁膨出|患女，55岁，4-0-1-4。...
0－1个月是乳儿期。
使用滴管时给0---1岁婴儿，以下哪点是正确的（）
关于0－1背包问题以下描述正确的是（）