背包问题|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]表示在第1~i的物品中花费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种情况,取较大值,即为第1~i的物品中花费j元的最大可能满意值。
不难发现,这种购买行为满足3个特点
1.最优子结构,即购买5件商品达到最大满意值时,
其中的任意件的购买总是也达到了最大值,可以独立求出。
2.无后效性,即前面购买不管怎样,
花费j元在前i个商品中的购买的最大满意值都不会变,
不会影响第i+1个商品的购买与否。
3.子问题有重叠性,即每一个物品的购买是独立的,不会干扰。
满足这三个特点的问题可以用动态规划(Dynamic Programming,DP)来解决
先找到问题的子问题的状态,再求出这些状态之间的转移方程,
再从最小的子问题开始着手解决问题。
在这里每种商品都只有买一件或不买2种状态,如果可以买任意件,又该如何呢?
想知道的话不要忘记点赞加关注,我是静静,我们下期再见。