【DP_背包专辑】

这短时间看了论文《背包九讲》，看到背包问题解法中的优美之处也看到背包问题在现实中的应用，总结出一句话：背包问题值得一看。

背包问题可以概括为这样的模型：有若干种选择，每种选择有一定的代价和价值，做某些选择会得到特定的状态，问我们在约定的条件下怎么得到特定的状态？这里的状态可以是代价和或者价值和或者由其他这两者组合而来的状态。这类问题需要枚举每种状态，但是可以通过动态规划减少枚举的次数，提高效率，主要思想是每次都利用前面得到的状态进行转移得到当前的状态。这类问题很少能用贪心的，首先，贪心很难证明策略是否正确，其次贪心必定使得枚举量大量减少，会导致结果错误。

个人认为背包九讲中的很多模型本质都是两种模型：01背包模型、完全背包模型。大家可以把这两种模型理解透彻，然后再看其他模型，这样必定事半功倍。

看《背包九讲》的过程中开了一个专题，大概26道题目，主要是Hdu和Poj的题目，题目有难有易，这次的专辑主要讲解这些题目，还有一些Uva的简单背包问题也会加入到这个专辑中。本专辑都只列举基本思路，如果大家想看详细思路或者代码请去我博客中查找，大部分题目我都有写解题报告。

一、01背包问题 (先枚举物品，再逆序枚举容量)

1、Hdu 2602 Bone Collector 非常常规的01背包问题，用一维和二维数组都可以做，一维快相当多。
2、Poj 3624 Charm Bracelet 赤裸裸的01背包问题
3、Hdu 2546 饭卡 n种菜选若干种使剩下的钱最少，背包容量是开始时的钱，物品体积是菜的价格，状态转移时记录答案。
4、Uva 624 CD 常规的01背包，但要输出路径，状态转移时记录当前状态下当前物品是否被选用，然后递归求解就好。
5、Uva 562 Dividing coins 平衡问题，将n个硬币的总价值累加得到sum，再用sum/2作为背包容量对n个硬币做01背包处理，看能组成的最大容量是多少。
6、Hdu 2955 Robberies （推荐)方案最优问题，需要一个简单地转换，我们求的是不被抓的概率而非被抓的概率，各个银行的储蓄总和为背包容量，体积为单个银
行 的储蓄，价值为不被抓概率。
7、Poj 2184 Cow Exhibition（推荐)变形的01背包，其实问题的本质是保证智商和幽默感和不为负数情况下的最大和。智商属性体积，幽默感属性为价值，问题转换为
求体积大等于0时的体积、价值总和。
8、Hdu 2639 Bone Collector II 求价值第K大的01背包问题，技巧是多加一维表示第k大时的价值，转移的时候用两个有序数列合并的方法不断更新第二维。
9、Poj 2923 Relocation（推荐，较综合) 用到状态压缩思想的01背包。先枚举选若干个时的状态，总状态量为1<<n，判断集合里的物品能否一次运走,如果能运走，那
就把这个状态看成一个物品。预处理完找到tot个物品，再对这tot个物品进行01背包处理，每个物品的体积是state[i]，价值是1，求必选n个物品的最少价值。状态转

移方程:dp[j|k] = min(dp[j|k],dp[k]+1) (k为state[i,1<=j<=(1<<n)-1])

10、Hdu 3466 Proud Merchants 与顺序有关的01背包，先按q-p排序再来处理，难想容易敲。（更新）

二、完全背包问题(先枚举物品，再正序枚举容量)

1、Uva 674 Coin Change完全背包求解方案数问题，只有5种硬币，基础题。

2、Uva 147 Dollars上一题的加强版，硬币有11种，另外这题用double输入，要考虑精度问题。

3、Poj 3181 Dollar Dayz必须 用高精度模拟的完全背包。

4、Poj 1787 Charlie's Change 这题本来是多重背包的题目，但是完全背包求解速度奇快。

5、Poj 3260 The Fewest Coins（推荐，较综合) 完全背包和多重背包混合题，先用完全背包预处理煤老板找钱的最小硬币数，再用多重背包求用到的最小硬币数。

6、Poj 2063 Investment求投资k年获得最大投资，每年都选最大利息的方案进行投资k年后就可以得到最多的人民币。

三、多重背包问题(先枚举物品，再正序枚举容量)

1、Hdu 1114 Piggy-Bank 简单多重背包，但当成01背包来暴力也完全没有问题，

2、Hdu 1059 Dividing简单多重背包，体积为硬币数，价值为币值，可用二进制处理成01背包求解，可用30对num进行优化。

3、Hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活标题超长超简单的多重背包，可用01背包求解。

4、Poj 1276 Cash Machine多重背包，需用二进制处理成01背包求解，体积是硬币数量，价值是币值。

5、Poj 2392 Space Elevator最大容量不定的多重背包，体积是每种木块的高度，由于可行性问题无价值这个概念。

四、分组背包问题(先逆序枚举容量，再枚举物品)

1、Hdu 1712 ACboy needs your help选课复习问题，没门课只能选一次，找个时间复习，求最大的收益。每门课对应一组，每个时间对应一个物品。

2、Hdu 3033 I love sneakers! xx买鞋问题，分组背包的变形，每种牌子至少选一双，这与分组的最多选一个不一样，但思想一样，物品为每种牌子的各种鞋子。

3、Poj 1837 Balance平衡问题，把每个砝码在每个位置的权值算出来，每个砝码一个分组，几个位置几个物品，最后求的是价值和为0的方案数。

4、Poj 3211 Washing ClothesShow幸福题，每种颜色的衣服的分到一组，费用是洗一件衣服的时间，每组求解出最少时间，再逐组累加起来。

5、Hdu 3810 Magina(推荐，综合)搜索加分组背包，分组背包必须用单调队列模拟，因为容量特别大，没办法按照常规进行转移。

6、Hdu 3535 AreYou Busy （推荐，混合背包)，各种背包混合，要求对01、完全、多重背包都有深入的理解。

五、树形背包问题(在树上进行分组背包处理)

1、Poj 1155 TELE 把每个节点的子节点看成一组背包，最大容量是这点的叶子子孙数量，选几个节点就是选择的容量，价值就是用户给的Money-中转费用。解题报告Here

2、Hdu 1011Starship Troopers和上题相似，要选择父节点必先子节点，特判m为0的时候。

3、Poj 1947 Rebuilding Roads求最少删除几条边使得子树节点个数为p，具体的模型和上题很像。解题报告Here

4、Hdu 1561 The more, The Better在一棵树上选择若干个点获得的最大价值，选子节点必须先选父节点，求解情况和上两题相同。解题报告Here

5、Hdu 4003 Find Metal Mineral(推荐，好题) 树形DP+选且只能选一个物品的分组背包，状态转移方程难想。解题报告here

6、Poj 2486 Apple Tree树形DP+分组背包，但是状态转移方程要分三步，较为难想。解题报告Here

7、Poj 3345 Bribing FIPA 树形DP+分组背包，和前面几题相比没有特殊的地方，只是要注意输入。具体可见Here

8、Hdu 4044 GeoDefense 树形DP+分组背包,要求从每个儿子结点获取最小的hp，然后找这些儿子的最大组合，不是特别好想。解题报告见Here

这篇文章将会不断更新，以后没遇到这五类背包，我都会整理进这个专题，希望大家保持关注。

本文ZeroClock原创，但可以转载，因为我们是兄弟。