背包问题|knapsack problem

视频版： https://www.bilibili.com/video/BV1pa4y1E7CC/

文字版：
在商店里面对着琳琅满目的商品，
再看看自己空瘪的钱包，
这么多自己想要的，
该怎么选择啊？
如何破除选择困难症？

大家好，
欢迎来到静谈算法，
我是静静。
不妨假设有5个想购买的物品，
分别是面包、快乐水、薯片、奶茶和月饼，有着不同的价格和满意值，
如何在10元的预算中获得最大的满意值呢？
为了方便考虑，我们假设最多购买一件
显然，这些东西被摆放在不同的货架上，不会被同时看见，选择是一步一步做的.
对于每一件商品，都有买或者不买2种可能的情况，
如果购买，那么满意值等于之前购买的商品的满意值加当前物品的满意值，
如果不买，那么满意值就是之前购买的商品的满意值。
同时，买与不买也影响着花费的钱。
不妨考虑一下这个例子。
对于第一个商品面包，花费7元及以上就可以购买，
同时获得9满意值（小于7元就算0满意值），
然后是快乐水，如果不买快乐水，那么满意值就等于上一行的值，
如果购买，满意值就是上一行的左侧2格的满意值加2，
以这一格为例，不购买就是花费7元买一个面包，满意值为9，
购买就是花费5元买面包（买不起为0满意），花2元买快乐水，
满意值为2。
比较9与2，取较大的值为9。
之后是薯片，同样的，比较花相同的钱的情况下，
买与不买薯片的2种情况中哪种满意值大。
接着是奶茶，最后是月饼。
这样的操作后，最右下角的就是可能的最大满意值。
为了便于书写，我们不妨用p[i]表示第i种物品的价格，
用v[i]表示第i种物品的满意值，
用dp[i][j]表示在第1i的物品中花费j元的最大可能满意值。
此时我们就可以写出公式为
买：dp[i][j]=v[i]+dp[i-1][j-p[i]]
即为花费p[i]元购买第i个商品的满意值与花费j-p[i]元在前i-1个商品中可能的最大满意值之和。
不买：dp[i][j]=dp[i-1][j]
即为花费j元在前i-1个商品中可能的最大满意值。
比较买与不买的2种情况，取较大值，即为第1i的物品中花费j元的最大可能满意值。
不难发现，这种购买行为满足3个特点
1.最优子结构，即购买5件商品达到最大满意值时，
其中的任意件的购买总是也达到了最大值，可以独立求出。
2.无后效性，即前面购买不管怎样，
花费j元在前i个商品中的购买的最大满意值都不会变，
不会影响第i+1个商品的购买与否。
3.子问题有重叠性，即每一个物品的购买是独立的，不会干扰。
满足这三个特点的问题可以用动态规划（Dynamic Programming，DP）来解决
先找到问题的子问题的状态，再求出这些状态之间的转移方程，
再从最小的子问题开始着手解决问题。
在这里每种商品都只有买一件或不买2种状态，如果可以买任意件，又该如何呢？
想知道的话不要忘记点赞加关注，我是静静，我们下期再见。