动态规划以及与贪心的区别

http://blog.csdn.net/u013445530/article/details/45645307

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。这句话暂时理解不了没关系，请看下面的例子:

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

贪心算法（每次选最大的）：

我们凭直观感觉告诉自己，先选面值最大，因此最多选2枚5元的硬币，现在是10元了，还差一元，接下来我们挑选第二大的3元硬币，发现不行（10+3=13超了），因此我们继续选第三大的硬币也就是1元硬币，选一个就可（10+1=11），所以总共用了3枚硬币凑够了11元。

但：

我们将面值改为2元，3元和5元的硬币，再用贪心法就不行了。

为什么呢？

按照贪心思路，我们同样先取2枚最大5元硬币，现在10元了，还差一元，接下来选第二大的，发现不行，再选第三大的，还是不行，这时用贪心方法永远凑不出11元，但是你仔细看看，其实我们可以凑出11元的，2枚3元硬币和1枚五元硬币就行了，这是人经过思考判断出来了的，但是怎么让计算机算出来呢？这就要用动态规划的思想：

动态规划：

首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？

为什么要这么问呢？两个原因：

1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。

2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

那么，我们用d(i)=j来表示凑够i元最少需要j个硬币。

即：

d(0)=0

d(1)=d(1-1)+1=d(0)+1=0+1=1

d(2)=d(2-1)+1=d(1)+1=1+1=2

d(3)=d(3-1)+1=d(2)+1=2+1=3 d(3)=d(3-3)+1=d(0)+1=0+1=1 d(3)=min{d(3-1)+1, d(3-3)+1}

d(i)表示状态状态转移方程的抽象 d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;

代码：

/*
动态规划：
需要拼凑的面额是sum，
凑够sum元所需要的面额的数目最少需要几张并输出
11,最少的硬币3个
输出： 1 2 1 2 1 2 3 2 3 2 3
分别是1—11元需要的最少的硬币数量
*/

int main()

{

int a[3] = {1,3,5},sum ,dp[12];

cin>>sum;

dp[0] = 0;

for(int i = 1; i <= sum; i++) dp[i] = i;

//我们假设存在1元的硬币那么i元最多只需要i枚1元硬币，当然最好设置dp[i]等于无穷大

for(int i = 1; i <= sum; i++)

{

for(int j = 0; j < 3; j++)

{

if(i >= a[j] && dp[i - a[j]] + 1 < dp[i])//当前最小

{

dp[i] = dp[i- a[j] ] + 1;

}

}

}

cout<<dp[sum]<<endl;

return 0;

}

此外，通过追踪我们是如何从前一个状态值得到当前状态值的，可以找到每一次我们用的是什么面值的硬币。比如，从上面的图我们可以看出，最终结果

d(11)=d(10)+1(面值为1)，而d(10)=d(5)+1(面值为5)，最后d(5)=d(0)+1 (面值为5)。所以我们凑够11元最少需要的3枚硬币是：1元、5元、5元。

可以说贪心问题是DP问题的特例

动态规划以及与贪心的区别

相关推荐