动态规划之背包.

Presentation on theme: "动态规划之背包."— Presentation transcript:

1 动态规划之背包

2 背包问题 容量有限 物品有价值 取物品遵循给定规则 求最大收益 状态定义 转移优化

3 01背包 Eason挖开一个矿洞里面有矿石，每个矿石有自己的体积C[i]和价值V[i]， Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石 O(NM)：用f[i][j]表示考虑1~i个物品花费j代价最大收益，转移过程为 f[i][j]=max{f[i-1][j],f[i-1][j-C[i]]+V[i]}

4 完全背包 Eason挖开一个矿洞里面有矿石，每种矿石有自己的体积C[i]和价值V[i]，每种都有无限 个。Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石 O(NM^2)：每个节点拆为若干个同样的物品再做01背包 O(NMlgM)：每个节点拆为大小分别为原来2^i倍的物品在做01背包 O(NM)：对于f[i][j]，令j=kC[i]+b，改for j = 0 to M为for b = 1 to C[i]和for k = 0 to M/C[i]

5 多重背包 Eason挖开一个矿洞里面有矿石，每种矿石有自己的体积C[i]和价值V[i]，每种有L[i]个。 Eason的背包只能装走总体积为M的矿石，问他最多能背走多少钱的矿石 O(NM)：利用具有单调性的队列对完全背包进行优化实现抛弃限制之外的状态以符合 题意

6 分组背包 Eason要开演唱会，但在每个省他只希望在一个城市献唱。每个城市的 演唱会耗时V[i]，带来收益C[i]。Eason时间有限，求最高收益。 O(NM)：f[i][j]表示考虑1~i组花费j的代价下的最大收益，转移时考虑N[i] 种选择物品的情况取最优结果

7 分组背包 Eason要开演唱会，但在每个省他不希望献唱耗时数超过L[i]。每个城市 的演唱会耗时V[i]，带来收益C[i]。Eason时间有限，求最高收益。 O(NM^2)：将每个组通过01背包做成某种泛化物品，求出该泛化物品的 价值函数W[i][j]表示第i组消耗j代价时能带来的收益。再通过类似与上题 的方法求解

8 树背包 Eason去摘苹果。有一颗苹果树，每个节点有一个质量为C[i]，美味度为V[i]的苹果。 Eason在爬树的过程中见到苹果就会吃掉，他最多能吃质量和一定的苹果，求最多能吃 到的美味度之和。 O(NM^2)：f[i][j]表示在以节点i为根的子树中消耗j代价的收益，根据分组背包自底向上 即可得到O(NM^2)的做法 O(NMlgN/N^2M)：f[i][j]表示考虑dfs序1~i的节点中且必须拿走i的情况下消耗代价j的最 大收益，通过f[father[i]][j-C[i]]+V[i]到f[i-1][j-C[i]]+V[i]向f[i][j]转移，以保证father[i]被取走