01背包问题
一、定义
01背包问题是在资源有限的情况下，实现收益最大化的一类问题。经典的场景是探险家偶然进入一片宝藏，每一件宝贝都是独一无二的，具有自己的价值和重量。由于背包容量有限，只能选择某几样宝贝。此类问题归属于 动态规划。
二、实现
直观来看，这是一个如何选择的问题。对一个宝贝i来说，是拿还是不拿，这是一个问题。
01背包问题的公式如下：
选择i的收益是
1 | 宝贝i的价值 |
不选择i的收益是
1 | 上一次选完宝贝后总的价值。即就当做没看见 i。 |
代码实现见 01packege
三、一点感触
01背包问题，归根结底是一个选择问题。选择了一个物品，获取价值的同时必然要承担它的负重，也会放弃一些选择其它物品的机会。程序里选错了可以重选，人生里选错了就不能重来。