通过这次比赛的题目来学习一下动态规划和背包问题
Question Less taolu
Description
1 |
|
#include
Input Description:
1 |
|
Output Description:
1 |
|
Answer
1 |
|
NOTE
记忆化搜索 :制表,查表,减少递归次数。通过解出并记录子问题的答案来求出父问题的答案
动态规划
Description
有N种物品(每种物品1件)和一个容量为V
的背包。放入第 i
种物品耗费的空间是Ci
,得到的价值是Wi
。求解将哪些物品装入背包可使价值总和最大。f[i][v]
表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。
Solution
决策为第i
个物品在前i-1
个物品放置完毕后,是选择放还是不放,状态转移方程为:
f[i][v] = max { f[i-1][v], f[i-1][v – Ci] +Wi }
解释 : 将前i件物品放入容量为v的背包中”这个子问题:
- 若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。
- 如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”。
- 如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”
- 此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
Example : 暴力遍历
1 |
|
Example : 动态规划
1 |
|
DP优于递归的好处:
动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。
通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化
存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增速时特别有用。