背包问题|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种状态，如果可以买任意件，又该如何呢？ 想知道的话不要忘记点赞加关注，我是静静，我们下期再见。