动态规划算法

在以前做ACM的时候, 总是绕不开DP算法解题, 刚好又在项目里遇到了, 就总结一下吧. DP算法又叫动态规划算法, 从字面可以看出它是动态的. 那么是什么样的动态呢, 可以这样理解: 根据之前的计算结果动态决定下一步的计算结果.

从一个简单的题目开始: 使用1,3,5三个数, 组成13, 需要的数字最少的方案. 一眼就能看出来是5 + 5 + 3. 那么从算法角度来看看这个是怎么实现的吧.

要判断13由多少构成, 那么就可以把问题看成为: 12, 10, 8这三个数分别最小由多少构成. 这样可以一直推到最小值1. 那么算法的步骤即从1开始计算最小构成值为多少.

0 = 0 -> 0不需要参数即可构成
1 = 0 + 1 => [1] -> 1个(1)即可构成
2 = 1 + 1 => [2] -> 第一个(1)是上一步的计算值, 第二个(1)是其中一个数
3 = 2 + 1 => [3]/ 0 + 3 => [1] -> 2 + 1中, (2)是上一步的计算值, 这里出现了分化, 3 可以由3个值构成, 也可以由1个值构成, 那么取小, 由1个值构成的供之后计算
4 = 3[1] + 1 => [2]/ 1[1] + 3 => [2]
5 = 4[2] + 1 => [3]/ 2[2] + 3 => [3]/ 0[0] + 5 => [1] -> 取小值1
6 = 5[1] + 1 => [2]/ 3[1] + 3 => [2]/ 1[1] + 5 => [2]
7 = 6[2] + 1 / 4[2] + 3 / 2[2] + 5 => [3]
8 = 7[3] + 1 / 5[1] + 3 / 3[1] + 5 => [2]
9 = 8[2] + 1 / 6[2] + 3 / 4[2] + 5 => [3]
10 = 9[3] + 1 => [4]/ 7[3] + 3 => [4]/ 5[1] + 5 => [2] -> 取小值2
11 = 10[2] + 1 / 8[2] + 3 / 6[2] + 5 => [3]
12 = 11[3] + 1 / 9[3] + 3 / 7[3] + 5 => [4]
13 = 12[4] + 1 => [5]/ 10[2] + 3 => [3]/ 8[2] + 5 => [3] -> 取小值3

而且可以从构成中看见, 13 = 10 + 3 / 8 + 5, 10 = 5 + 5, 8 = 5 + 3

这便是动态规划算法的原理, 现在用代码来实现一遍:

int lis(int n){ //计算n由最少多少个数字构成
    int *d  = new int[n + 1]; //计算出0-n的全部
    int a[] = {1, 3, 5};
    d[0] = 0; //和为0的时候不需要元素构成
    for (int i = 1; i <= n; i++){ //从i计算到n
        d[i] = d[i - 1] + 1; //1为最小元素, 默认为前一个值减最小值加1
        for (int j = 0; j < 3; j++){ //循环所有元素
            if (a[j] <= i && d[i - a[j]] + 1 < d[i]){ // 如果n-某元素所需要的构成比当前构成小, 那么取小的构成
                d[i] = d[i - a[j]] + 1;
            }
        }
    }
    return d[n]; // 返回构成的最小值
}

接下来看一个复杂一点的问题: 有编号分别为 a,b,c,d,e 的五件物品, 它们的重量分别是 2,2,6,5,4, 它们的价值分别是 6,3,5,4,6, 现在给你个承重为 10 的背包, 如何让背包里装入的物品具有最大的价值总和.

同样的计算方式:

int lis(int n){ //计算 n 重量时的最大价值
int w[] = { 0, 4, 5, 6, 2, 2 };
int v[] = { 0, 6, 4, 5, 3, 6 };
int w*length = getArrayLen(w);
int \*\_d = new int*[w_length];
for (int i = 0; i < w_length; i++){
d[i] = new int[n + 1]; // 计算出 0-n 的全部
}
for (int i = 0; i < n + 1 || i < w_length; i++){
if (i < n + 1){
d[0][i] = 0; // 初始化 0-0 的元素值为 0
}
if (i < w_length){
d[i][0] = 0; // d[x][n]表示放置之前的 x 号物体时, n 承重的时候的价值
}
}
for (int i = 1; i < n + 1; i++){ // 主循环
for (int j = 1; j < w_length; j++){ // 遍历每个物体, 填充 d[x], 即当前含有前 j 个物体时的计算承重价值
if (i >= w[j]){ // 如果当前承重大于物品重量
int a = d[j - 1][i]; // a 为 放置上一个物体时, 承重的价值
int b = d[j - 1]i - w[j]] + v[j]; // b 为 放置之前的物体情况下, 如果承重减去当前物体承重, 再加上当前物体的价值 的价值
d[j][i] = a > b ? a : b; // 取价值比较大的值
}
else{ // 如果当前承重小于物品重量, 那么直接和上一个承重的价值相等
d[j][i] = d[j - 1][i];
}
}
}
return d[w_length - 1][n]; // 放置全部物体的情况下, n 承重的价值
}

printf("%4d\n", lis(10)); // -> 15