详解背包问题(DP分支）

目录

什么是背包问题？ 

所以我编了些例题：

例题一： 

例题二：

例题三：

这三种经典例题对应的题解如下：

水题，变形例题以及其他背包们：

水题们：

0/1背包：

完全背包：

多重背包：

变形例题：

0/1背包：

完全背包：

其他背包

什么是背包问题？ 

要吃透背包问题，就得先知道背包问题是个啥，所以我从百度摘了些内容：

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。

背包问题已经研究了一个多世纪，早期的作品可追溯到1897年数学家托比亚斯·丹齐格（Tobias Dantzig，1884-1956）的早期作品，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。

是不是感觉很晦涩很难懂？

所以我编了些例题：

例题一： 

小李子的摸底测考试成绩出来了，他的进步很大！所以他的爸妈决定带着高兴的小李子前往阿穷便利店进行零食大采购！每种零食都会有它的价格和它对于小李子的价值，由于他爸妈严格的价格限制，他只能在价格限制中购买零食。你作为他就在刚刚结实的好朋友，能够使他在价格限制中获取最高的价值吗？(从便利店的名字里就能够看出来，这家便利店十分贫穷，所以老板要求每种零食只能买一份）

例题二：

小李子的期中考试成绩出来了，他得了100分！所以他的爸妈决定带着几近疯狂的小李子前往富丽堂皇便利店进行疯狂零食大采购！每种零食都会有它的价格和它对于小李子的价值，由于他爸妈严格的价格限制，他只能在价格限制中购买零食。你作为他就在刚刚结实的好朋友，能够使他在价格限制中获取最高的价值？(从便利店的名字里就能够看出来，这家便利店十分富裕，所以老板同意每种零食可以买无数份）

例题三：

小李子的期中考试成绩出来了，他得了98分！所以他的爸妈决定带着开心的小李子前往富丽堂皇便利店进行超级零食大采购！每种零食都会有它的价格和它对于小李子的价值，由于他爸妈严格的价格限制，他只能在价格限制中购买零食。你作为他就在刚刚结实的好朋友，能够使他在价格限制中获取最高的价值吗？(从便利店的名字里就能够看出来，这家便利店十分富裕，所以老板同意每种零食可以买无数份，可是因为小李子退步了一些，所以他爸妈给每种零食都设置了一个购买数量的限额）

很多眼尖的大佬可能就已经看出来了，这三道题分别就是0/1背包，完全背包以及多重背包的经典例题，可以说大多数背包问题都是这三种。

这三种经典例题对应的题解如下：

0/1背包

完全背包

多重背包

看懂了这些例题，接下来就请出我们亲爱的

水题，变形例题以及其他背包们：

水题们：

0/1背包：

开心的金明

由于采药实在太水了就没有写

完全背包：

竞赛总分

疯狂的采药

多重背包：

逃亡的准备

变形例题：

0/1背包：

演讲大厅安排

饥饿的牛

5 倍经验日

完全背包：

最小乘车费用

火车票

单词的划分

其他背包：

货币系统

对抗赛

砝码称重

—————————————————————~end~———————————————————