主要内容 #
- 从一个例子说起
- 最优化原理
- 无后效性原则
1. 从一个例子说起 #
先来看看生活中经常遇到的事吧——假设你是个土豪,身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w,需要用到尽量少的钞票。
依据生活经验,我们显然可以采取这样的策略:能用100的就尽量用100的,否则尽量用50的……依次类推。在这种策略下,666=6×100+1×50+1×10+1×5+1×1,共使用了10张钞票。
这种策略称为“贪心”:假设我们面对的局面是“需要凑出w”,贪心策略会尽快让w变得更小。能让w少100就尽量让它少100,这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明,贪心策略是正确的。
但是,如果我们换一组钞票的面值,贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11,那么我们在凑出15的时候,贪心策略会出错:
15=1×11+4×1(贪心策略使用了5张钞票) 15=3×5 (正确的策略,只用3张钞票)
贪心策略的纲领是:“尽量使接下来面对的w更小”。这样,贪心策略在w=15的局面时,会优先使用11来把w降到4;但是在这个问题中,凑出4的代价是很高的,必须使用4×1。如果使用了5,w会降为10,虽然没有4那么小,但是凑出10只需要两张5元。 在这里我们发现,贪心是一种只考虑眼前情况的策略
重新分析刚刚的例子。w=15时,我们如果取11,接下来就面对w=4的情况;如果取5,则接下来面对w=10的情况。我们发现这些问题都有相同的形式:“给定w,凑出w所用的最少钞票是多少张?”接下来,我们用f(n)来表示“凑出n所需的最少钞票数量”。 那么,如果我们取了11,最后的代价(用掉的钞票总数)是多少呢?
明显cost=f(4)+1=4+1=5,它的意义是:利用11来凑出15,付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。 依次类推,马上可以知道:如果我们用5来凑出15,cost就是f(10) + 1 = 2 + 1 = 3。
那么,现在w=15的时候,我们该取那种钞票呢?当然是各种方案中,cost值最低的那一个!
取11 -cost = f(4)+1 = 4+1=5 取10 -cost = f(5)+1 = 2+1=3 取1 -cost = f(14)+1 = 4+1=5
显而易见,cost值最低的是取5的方案。我们通过上面三个式子,做出了正确的决策!
这给了我们一个至关重要的启示—— f(n)只与 f(n−1),f(n−5),f(n−11) 相关;更确切地说:
f(n)=min{f(n−1),f(n−5),f(n−11)}+1
这个式子是非常激动人心的。我们要求出f(n),只需要求出几个更小的f值;既然如此,我们从小到大把所有的f(i)求出来不就好了?注意一下边界情况即可。代码如下:
#include<iostream> using namespace std; int main(){ int f[105], i, n, cost; cin >> n; f[0] = 0; for(int i = 1; i <= n; i++){ cost = INT_MAX; if(i - 1 >= 0) cost = min(cost, f[i - 1] + 1); if(i - 5 >= 0) cost = min(cost, f[i - 5] + 1); if(i - 11 >= 0) cost = min(cost, f[i - 11] + 1); f[i] = cost; cout << f[i] << endl; } }
我们以 O(n)的复杂度解决了这个问题。现在回过头来,我们看看它的原理:
– f(n)只与f(n−1),f(n−5),f(n−11)的值相关。
– 我们只关心 f(w)的值,不关心是怎么凑出w的。
这两个事实,保证了我们做法的正确性。它比起贪心策略,会分别算出取1、5、11的代价,从而做出一个正确决策,这样就避免掉了“鼠目寸光”
这就是DP(动态规划,dynamic programming).
将一个问题拆成几个子问题,分别求解这些子问题,即可推断出大问题的解。
2. 最优化原理 #
回顾我们对f(n)的定义:我们记“凑出n所需的最少钞票数量”为f(n).
f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解,我们即可算出w=15的最优解。
大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”。
引入这两个概念之后,我们如何判断一个问题能否使用DP解决呢?
能将大问题拆成几个小问题,且满足无后效性、最优子结构性质。
3. 无后效性原则 #
一旦f(n)确定,“我们如何凑出f(n)”就再也用不着了。
要求出f(15),只需要知道f(14),f(10),f(4)的值,而f(14),f(10),f(4)是如何算出来的,对之后的问题没有影响。
“未来与过去无关”,这就是无后效性。
严格定义:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。