01背包问题

一、定义

01背包问题是在资源有限的情况下,实现收益最大化的一类问题。经典的场景是探险家偶然进入一片宝藏,每一件宝贝都是独一无二的,具有自己的价值和重量。由于背包容量有限,只能选择某几样宝贝。此类问题归属于 动态规划

二、实现

直观来看,这是一个如何选择的问题。对一个宝贝i来说,是拿还是不拿,这是一个问题。 01背包问题的公式如下: 01背包问题公式

选择i的收益是

宝贝i的价值
+
为了选择i,背包容量减少为背包容量 - 宝贝i的重量,这时能装的宝贝的价值

不选择i的收益是

上一次选完宝贝后总的价值。即就当做没看见i。

代码实现见 01packege

三、一点感触

01背包问题,归根结底是一个选择问题。选择了一个物品,获取价值的同时必然要承担它的负重,也会放弃一些选择其它物品的机会。程序里选错了可以重选,人生里选错了就不能重来。

四、参考链接

动态规划:背包问题

动态规划 之 0-1背包问题

动态规划之01背包问题(最易理解的讲解)

Published: September 21 2018

blog comments powered by Disqus