[置顶] 【DP_背包专辑】【8、1最新更新】

      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排序再来处理，难想容易敲。

       11、Hdu 2126 Buy the souvenirs  n个物品，m元钱，每个物品最多买一次，问最多可以买几件物品，并且输出方案数。加一维表示已经买几件物品。

      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年后就可以得到最多的人民币。

      7、 3623、Battle Ships   建塔打大怪兽，有n种塔，任意建多少个，建塔有时间，建好的塔可以一直打怪兽。把时间当作容量，把打对方多少血当作价值。

     8 、Zoj 3524 Crazy Shopping (推荐)  拓朴排序+完全背包，先拓朴排序，注意可能有好几个起点，然后按照拓扑序转移，每转移一次就对下一个点进行完全背包，同时注意更                                                                      新所用的能量。 （8、1号更新)

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

      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 Clothes Show幸福题，每种颜色的衣服的分到一组，费用是洗一件衣服的时间，每组求解出最少时间，再逐组累加起来。

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

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

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

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

       2、Hdu 1011  Starship 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
        9、Zoj 3627 Treasure Hunt II  树形DP +分组背包，浙大月赛的水题，很普通的树形背包。