关于动态规划的一些经典例子

发表于 | | 阅读次数:

研究了一天的我废话已经不想多说了。。。智商有限，直接切入正题，动态规划 很有用，嗯 很有用。
还是多说一句，我感觉其实动态规划不该说是一种算法，而是一种思想，一种优化问题解决办法的思想~o(￣▽￣)o

硬币问题

由一个简单的硬币问题引入，题目如下
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？
这个问题可以这么看，本质凑i元。i <11,i = 0，即我们需要0个硬币来凑够0元。算法嘛，抽象成规律化简化问题是重点，那么，我们用d(i) = j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0) = 0，表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用，拿起一个面值为1的硬币，接下来只需要凑够0元即可，而d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。当i=2时，仍然只有面值为1的硬币可用，拿起一个面值为1的硬币，接下来只需要再凑够2-1=1元即可，而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。当i=3时，能用的硬币就有两种了：1元的和3元的。就有两种方案。如果拿了一个1元的硬币，接下来就该想凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。第二种方案是拿一个3元的硬币，接下来就要求凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1.要求是用最少的硬币数量来凑够3元。所以选择d(3)=1。具体应该是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。
从以上的文字中可以抽象出动态规划里非常重要的两个概念：状态和状态转移方程。
上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的”状态”根据子问题定义状态。既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。这就是状态转移方程，用于描述状态之间是如何转移的。
抽象一下d(i)=min{d(i-vj)+1}，其中i-vj>=0，vj表示第j个硬币的面值;
有了状态和状态转移方程，这个问题基本上也就解决了。

通过追踪如何从前一个状态值得到当前状态值，可以找到每一次我们用的是什么面值的硬币。比如，从上面的图我们可以看出，最终结果，而d(10)=d(5)+1(面值为5)，最后d(5)=d(0)+1 (面值为5)。所以我们凑够11元最少需要的3枚硬币是：1元、5元、5元。

最长非降子序列（LIS）

应该是讲dp最经典的例子了，但是网上大多数解析我的亲娘啊就是感觉懂的懂，不懂得还是不懂，估计是我感冒状态懵比中脑子不太好使，此处抹一把鼻涕，让我们进入重点，敲黑板，重点啊
题目是这样的
给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4.
当处理到2时，以5,6,7,1,2为末尾元素的最长递增序列分别为
5
5,6
5,6,7
1
1,2
当新加入最后一个元素8时，这些序列变为
5,8
5,6,8
5,6,7,8
1,8
1,2,8
其中最长的递增序列为5,6,7,8，长度为4。当然别的数组中也可能出现相同长度的最长递增序列。
其实这个算法的思想十分简单，如果要得出Ai序列的最长递增子序列，就需要计算出Ai-1的所有元素作为最大元素的最长递增序列，依次递推Ai-2，Ai-3，……，将此过程倒过来，即可得到递推算法，依次推出A1，A2，……，直到推出Ai为止 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
unsigned int LISS(const int array[], size_t length, int result[])  
{  
    unsigned int i, j, k, max;  
  
    //变长数组参数，C99新特性，用于记录当前各元素作为最大元素的最长递增序列长度  
    unsigned int liss[length];  
  
    //前驱元素数组，记录当前以该元素作为最大元素的递增序列中该元素的前驱节点，用于打印序列用  
    unsigned int pre[length];  
  
    for(i = 0; i < length; ++i)  
    {  
        liss[i] = 1;  
        pre[i] = i;  
    }  
  
    for(i = 1, max = 1, k = 0; i < length; ++i)  
    {  
        //找到以array[i]为最末元素的最长递增子序列  
        for(j = 0; j < i; ++j)  
        {  
            //如果要求非递减子序列只需将array[j] < array[i]改成<=，  
            //如果要求递减子序列只需改为>  
            if(array[j] <= array[i] && liss[j] + 1> liss[i])  
            {  
                liss[i] = liss[j] + 1;  
                pre[i] = j;  
  
                //得到当前最长递增子序列的长度，以及该子序列的最末元素的位置  
                if(max < liss[i])  
                {  
                    max = liss[i];  
                    k = i;  
                }  
            }  
        }  
    }  
  
    //输出序列  
    i = max - 1;  
  
    while(pre[k] != k)  
    {  
        result[i--] = array[k];  
        k = pre[k];  
    }  
  
    result[i] = array[k];  
  
    return max;  
}

至于想问为啥不从第一个开始只一趟循环找到递增的序列的孩纸，我只能说 面壁思过去(“▔□▔)…

01背包问题

经典的01背包问题是这样的：

有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]
多哈皮啊，你看诶你看诶，每个东西只有两种状态，要么取要么不取。状态转移方程呢就是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
怎么理解介玩意儿咧？f[i][v]就是说容量为v的背包，在放第i个东西，嗯是正在的在不是byebye的再，现在需要放置的是第i件物品，这件物品的体积是c[i],价值是w[i]，而对于一个物品，只有放和不放两种状态，f[i-1][v]就是说，不放了！老子不要！那另一个就是说，这东西老子要了。
而这两个选择的价值是不一样的，不放的下一步又有更优的价值，或者放了的下一步结果有更优值。选这两种中价值最高的一种。
理解了这个方程后，将方程代入实际题目的应用之中，可得

1
2
3
4
5
6
7
for(i = 1; i<=n; i++)  
{  
    for(j = v; j>=c[i]; j--) 
    {  
        f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);  
    }  
}

这是二维的解法，二维中第二层循环递增或递减结果都是一样的，但是如果换成一维第二层循环一定要是递减，以免拿的物品重复。以下是一维的解法： 

1
2
3
for (int i=0;i<N;i++)
   for (int j=M;j>=need[i];j--)
       dp[j]=max(dp[j],dp[j-need[i]]+value[i]);//逆序才能保证背包中每次放入物品都是一次，即d[j]和dp[j-need[i]]+value[i]分别表示f[i-1][v],f[i-1][v-c[i]]+w[i]

金矿模型

题目

接下来我们在看一个金矿问题，都是背包模型的
有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了十座金矿，并且这十座金矿在地图上排成一条直线，国王知道这个消息后非常高兴，他希望能够把这些金子都挖出来造福国民，首先他把这些金矿按照在地图上的位置从西至东进行编号，依次为0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘测，以便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子，然后动员国民都来挖金子。

  • 题目补充1：挖每一座金矿需要的人数是固定的，多一个人少一个人都不行。国王知道每个金矿各需要多少人手，金矿i需要的人数为peopleNeeded[i]。
  • 题目补充2：每一座金矿所挖出来的金子数是固定的，当第i座金矿有peopleNeeded[i]人去挖的话，就一定能恰好挖出gold[i]个金子。否则一个金子都挖不出来。
  • 题目补充3：开采一座金矿的人完成开采工作后，他们不会再次去开采其它金矿，因此一个人最多只能使用一次。
  • 题目补充4：国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人，因此这些人可能不够把所有的金子都挖出来，但是国王希望挖到的金子越多越好。
  • 题目补充5：这个国家的每一个人都很老实（包括国王），不会私吞任何金子，也不会弄虚作假，不会说谎话。
  • 题目补充6：有很多人拿到这个题后的第一反应就是对每一个金矿求出平均每个人能挖出多少金子，然后从高到低进行选择，这里要强调这种方法是错的，如果你也是这样想的，请考虑背包模型，当有一个背包的容量为10，共有3个物品，体积分别是3、3、5，价值分别是6、6、9，那么你的方法取到的是前两个物品，总价值是12，但明显最大值是后两个物品组成的15。
  • 题目补充7：我们只需要知道最多可以挖出多少金子即可，而不用关心哪些金矿挖哪些金矿不挖。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
=========程序信息========
对应题目：01背包之金矿模型
使用语言：c++
使用编译器：Visual Studio 2005.NET
使用算法：动态规划
算法运行时间：O(people * n) [people是人数，n是金矿数]
作者：贵州大学05级 刘永辉 
昵称：SDJL
编写时间：2008年8月
联系QQ：44561907
E-Mail：44561907@qq.com
获得更多文章请访问我的博客：www.cnblogs.com/sdjl
如果发现BUG或有写得不好的地方请发邮件告诉我:)
转载请保留此部分信息:)
*/
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
const int max_n = 100;//程序支持的最多金矿数
const int max_people = 10000;//程序支持的最多人数
int n;//金矿数
int peopleTotal;//可以用于挖金子的人数
int peopleNeed[max_n];//每座金矿需要的人数
int gold[max_n];//每座金矿能够挖出来的金子数
int maxGold[max_people][max_n];//maxGold[i][j]保存了i个人挖前j个金矿能够得到的最大金子数，等于-1时表示未知
//初始化数据 
void init()
{
    ifstream inputFile("beibao.in");
    inputFile>>peopleTotal>>n;
    for(int i=0; i<n; i++)
        inputFile>>peopleNeed[i]>>gold[i];
    inputFile.close();
            
    for(int i=0; i<=peopleTotal; i++)
        for(int j=0; j<n; j++)
            maxGold[i][j] = -1;//等于-1时表示未知 [对应动态规划中的“做备忘录”]
        
}
//获得在仅有people个人和前mineNum个金矿时能够得到的最大金子数，注意“前多少个”也是从0开始编号的
int GetMaxGold(int people, int mineNum)
{
    //申明返回的最大金子数
    int retMaxGold;
    //如果这个问题曾经计算过  [对应动态规划中的“做备忘录”]
    if(maxGold[people][mineNum] != -1)
    {
        //获得保存起来的值
        retMaxGold = maxGold[people][mineNum];
    }
    else if(mineNum == 0)//如果仅有一个金矿时 [对应动态规划中的“边界”]
    {
        //当给出的人数足够开采这座金矿
        if(people >= peopleNeed[mineNum])
        {    
            //得到的最大值就是这座金矿的金子数
            retMaxGold = gold[mineNum];
        }
        else//否则这唯一的一座金矿也不能开采
        {
            //得到的最大值为0个金子
            retMaxGold = 0;
        }
    }
    else if(people >= peopleNeed[mineNum])//如果给出的人够开采这座金矿 [对应动态规划中的“最优子结构”]
    {
        //考虑开采与不开采两种情况，取最大值
        retMaxGold = max(GetMaxGold(people - peopleNeed[mineNum],mineNum -1) + gold[mineNum],
                                        GetMaxGold(people,mineNum - 1));
    }
    else//否则给出的人不够开采这座金矿 [对应动态规划中的“最优子结构”]
    {
        //仅考虑不开采的情况
        retMaxGold  = GetMaxGold(people,mineNum - 1);
    }
    
    //做备忘录    
    maxGold[people][mineNum] = retMaxGold;
    return retMaxGold;
}
int _tmain(int argc, _TCHAR* argv[])
{
    //初始化数据
    init();
    //输出给定peopleTotal个人和n个金矿能够获得的最大金子数，再次提醒编号从0开始，所以最后一个金矿编号为n-1
    cout<<GetMaxGold(peopleTotal,n-1);
    system("pause");
    return 0;
}

这个博主写的这篇动态规划的文章很好，推荐，传送门 博客地址
后续研究背包专题