数据结构与算法学习笔记（2）——动态规划

发表于   |   分类于   |  

本章讲一讲动态规划的基础。

本文仅供个人记录和复习，不用于其他用途

背包问题

话说一天晚上，有一个小偷悄悄地进入了一家珠宝店，珠宝店里有着各式各样的宝石。但是呢，由于他的背包体积有限，所以他只能带走一部分宝石。那么，如何选择才能使小偷带走的宝石是价值最高的呢？有的人可能会说，我只挑那些价值最高的宝石不就可以了吗？然而，价值高的宝石并不代表着它是最好的选择。这个问题有一个限制条件，那就是小偷的背包有体积限制。所以，我们在考虑问题时必须同时考虑价值和体积两个方面。

如何选择

事实上，如果宝石价值高同时体积也大，那么它每一体积所占的价值并不是最高的，这里我用一个词来描述这个概念，那就是性价比。我们最好的选择并不一定是价值最高的宝石，而可能那些性价比最高的宝石。那么问题来了，我们是不是只装性价比最高的宝石呢？这看起来确实是一种明智的选择，但是，还是那个问题，小偷的背包体积有限，而且并不一定能够刚好装满。我们遇到的问题有下面几个：

  • 到底是选择性价比高的宝石还是价值高的宝石
  • 把背包装满好还是不装满好

我之所以用可能这个词，是因为全部选择性价比高的宝石并不一定是最好的选择。你可能又会奇怪，性价比高不是最好吗？但是呢，宝石的体积不同，我们如果全部选择性价比高的宝石，不一定能将背包刚好装满。那么，如果我们选择体积大价值大的宝石，可能会比选择几个性价比高的宝石要更好。仔细思考你会发现，这个问题很复杂，直接想是很难得出答案的。因此，我们最好将大的问题缩小成一个同类型的问题，那么这也就是动态规划的核心。

动态规划方程

假如有i个宝石，宝石从0到i-1编号，背包的体积为j，w[i]表示第i号宝石的价值，v[i]表示第i号宝石的体积。我们规定d[i][j]代表的是用j体积的背包装入i个宝石所能得到的最大价值。我们现在试着将问题缩小，考虑装入第i-1号宝石的情况：

  • 如果不装第i-1号宝石，那么d[i][j]就等于d[i - 1][j]
  • 如果装入第i-1号宝石，那么d[i][j]就等于d[i - 1][j - v[i - 1]] + w[i - 1]
  • 在能够装入第i-1号宝石的前提下，装与不装哪个的价值大

其实最关键的就是第三个情况，我们需要判断装还是不装。当然，这个是最后一块宝石，能够装进去的话当然要装。事实上，我们需要考虑是前面的情况，那就是对于第i-2号宝石，我们应不应该装？对于第i-2号宝石，我们又需要考虑第i-3号宝石。当我们将问题缩小到最小时，我们能够很简单的得出一个答案。那么，参考递归的思想，反过来便能够推出最终的结果。动态规划实际上就是通过局部最优解来推出全局最优解，而所谓的动态规划方程就是解决问题的方法。

我们首先找到一个变化的状态，在这里就是d[i][j]。然后找到动态规划方程，在这里就是max{d[i - 1][j], d[i - 1][j - v[i - 1]] + w[i - 1]}，也就是装与不装哪个价值大。只要找到了动态规划方程，问题就很简单了。

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
#include <stdio.h>
int v[1000];          // 记录宝石的体积
int w[1000];          // 记录宝石的价值
int x[1000];          // 记录宝石是否装入背包，0为未装入，1为装入
int d[1000][100000];  // 记录用j体积的背包装入i个宝石所能得到的最大价值
int getMax(int i, int j)
{
    int w1 = d[i][j];                            // 不装入i - 1号宝石
    int w2 = d[i - 1][j - v[i - 1]] + w[i - 1];  // 装入i - 1号宝石
    return w1 > w2 ? w1 : w2;
}
int main()
{
    int n, c;  // 记录宝石数量和背包体积
    int i, j;
    scanf("%d%d", &n, &c);
    // 读入宝石的体积和价值，宝石从0开始计数
    for(i = 0; i < n; i++)  
    {
        scanf("%d%d", &v[i], &w[i]);
    }
    
    // 最大价值d从1开始计数，i为0时直接等于0
    for(i = 0; i <= n; i++)  
    {
        for(j = 0; j <= c; j++)
        {
            d[i][j] = i == 0 ? 0 : d[i - 1][j];  // i为0，最大价值为0，否则便初始化为前一子问题的值
            if(i > 0 && j >= v[i - 1])           // 只有当宝石能够装进背包剩下空间时，才去考虑装进去的价值大还是不装的价值大
            {
                d[i][j] = getMax(i, j);
            }
        }
    }
    printf("最大价值为：%d\n", d[n][c]);
    // 判断宝石是否装入背包
    for(i = n, j = c; i > 0; --i)  
    {
        if(d[i][j] > d[i - 1][j])
        {
            x[i - 1] = 1;
            j = j - v[i - 1];  // 装入第i-1个宝石后背包能装入的体积就只剩下j - v[i-1]
        }
    }
    for(i = 0; i < n; i++)
    {
        printf("%d ", x[i]);
    }
}