搜索

动态规划

动态规划

0. 导引

一个问题能用动态规划解决，必须具有以下两个基本条件：

  • 最优子结构
  • 重叠子问题

算法导论中提到，动态规划有两种等价的实现方法。第一种是自底向上的递推迭代，第二种是带备忘录的自顶向下（带备忘录的递归，如果某个阶段已经计算过，那么直接结束递归）。

还有一个比较重要的是要求子问题间无后效性。有些问题可能不满足这个，或者证明比较麻烦。

下面看个例子。

根据这个递归公式，

  • 自底向上：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int W(int a, int b){
    for(int i = 0; i <= a; i++){
        for(int j = 0; j <= b; j++){
            if(i == 0 || j == 0){
                dp[i][j] = 1;
                continue;
            }
            if(i < j){
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
            }else{
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
	}
    return dp[a][b];
}
  • 带备忘录的自顶向下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int W(int a, int b){
    if(a <= 0 || b <= 0){
        return 1;
    }
    if(dp[a][b] != 0){
        return dp[a][b];
    }

    if(a < b){
        dp[a][b] = W(a - 1, b - 1) + W(a, b - 1);
    }else
        dp[a][b] = W(a - 1, b - 1) + W(a - 1, b);
    return dp[a][b];
}

更多练习，http://acm.hdu.edu.cn/showproblem.php?pid=1579

1. 最大子段和

状态转移方程：

$\tt dp[i]$表示到以第 $\tt i$ 个元素结尾的最大子连续段和。

leetcode 53号问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int dp[] = new int[len];
        dp[0] = nums[0];
        int ans = dp[0];
        for(int i = 1; i < len; i++){
            //第i个dp元素代表以i结尾的最大连续子序和
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}

进阶1：现在给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵，输出最大的元素总和。题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1081（杭电这个数据有点水....）

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 <cstdio>
#include <iostream>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;

int n, matrix[105][105], dp[105][105];
int main ()
{
    /**
    思路: 前缀和 + 动态规划
    遍历每一个"行对",然后扫描1-n列
    数组dp[m][n]保存的是第n列，前m行的所有数的和，这样就把列压缩了成了一维的最大子段和
    这样只要扫描所有行对就能找到最大的子矩阵的和。
    时间复杂度：O(r^2c);
    */
    while(cin >> n){
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin >> matrix[i][j];
                if(i == 1){//第一行
                    dp[i][j] = matrix[i][j];
                }
            }
        }
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i-1][j] + matrix[i][j];
            }
        }
        int maxn = INT_MIN;
        for(int i = 1; i <= n; i++){//遍历所有行对
            for(int j = i; j <= n; j++){
                //一维的最大子段和
                int sum = 0;
                for(int c = 1; c <= n; c++){//注意数组的意义
                    //第c列的前i行到j行的前缀和
                    int tmp = dp[j][c] - dp[i-1][c];
                    if(sum <= 0){
                        sum = tmp;
                    }else
                        sum += tmp;
                    maxn = max(sum, maxn);
                }
            }
        }
        cout << maxn << endl;
    }
    return 0;
}

变形：题目同上，不同的是最后输出最大子矩阵的左上角的行号和列号以及右下角的行号和列号。题目链接：https://leetcode-cn.com/problems/max-submatrix-lcci/

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
class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        
        int row = matrix.length;
        int col = matrix[0].length;
        int ans[] = new int[4];
        int dp[][] = new int[row + 1][col + 1];
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(i == 0){
                    dp[i+1][j+1] = matrix[i][j];
                }
            }
        }
        for(int i = 1; i < row; i++){
            for(int j = 0; j < col; j++){
                dp[i+1][j+1] = dp[i- 1 + 1][j + 1] + matrix[i][j];
            }
        }
        int maxn = Integer.MIN_VALUE;
        int begin = 1;
        for(int i = 1; i <= row; i++){
            for(int j = i; j <= row; j++){
                int sum = 0;
                for(int cc = 1; cc <= col; cc++){
                    int tmp = dp[j][cc] - dp[i-1][cc];
                    //还需记录最大子段和的起止点
                    if(sum <= 0){//这个判断条件坑死我了....
                        sum = tmp;
                        begin = cc;
                    }else{
                        sum += tmp;
                    }
                    if(sum > maxn){
                        maxn = sum;
                        ans[0] = i - 1;//左上角行号
                        ans[1] = begin - 1;
                        ans[2] = j - 1;//右下角行号
                        ans[3] = cc - 1;//右下角列号
                    }
                }
                
            }
        }
        
        return ans;
    }
}

2. 最长上升子序列

状态转移方程：

$\tt dp[i]$表示以第 $\tt i$ 个元素结尾的序列的最长上升子序列。

$\tt Leetcode$ 第300号题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0 || nums == null)
            return 0;
        if(nums.length == 1)
            return 1;
       int dp[] = new int[nums.length];
        int max = 1;
        for(int i = 0; i < nums.length; i++)
            dp[i] = 1;
        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);//理解+1操作
                    max = Math.max(dp[i], max);
                }
            }
        }
        return max;
    }
}

进阶：编写算法，求出一个数字序列中最长递增子序列的个数。这是Leetcode 673号问题。

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
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        int dp[] = new int[len + 1];
        //需要利用一个counter数组记录每个数字的最长递增序列的组合数是多少
        int counter[] = new int[len + 1];
         int maxn = -1, res = 0;
        for(int i = 0; i < len; i++){
            dp[i] = 1;
            counter[i] = 1;//自身为一个序列，只有一种组合数
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    if (dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        counter[i] = counter[j];
                    }else if (dp[j] + 1 == dp[i]){
                        counter[i] += counter[j];
                    }
                }
            }
            maxn = Math.max(dp[i], maxn);
        }
        for (int i = 0; i < len; i++){
            if (dp[i] == maxn){
                res += counter[i];
            }
        }
        return res;
    }
}

3. 最长公共子序列(lcs)

状态转移方程：

提高：现在不仅要求出最长公共子序列的长度，还要求输出最长公共子序列，该怎么办？

题目链接：http://www.51nod.com/Challenge/Problem.html#problemId=1006

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
#include <iostream>
#include <cstring>
using namespace std;
int dp[1005][1005], flag[1005][1005];
char s1[1005],s2[1005];
void printLCS(int i, int j){
    if(i <= 0 || j <= 0){
        return ;
    }
    if(flag[i][j] == 0){
        printLCS(i-1,j-1);
        cout << s1[i-1];
    }else if(flag[i][j] == 1){
        printLCS(i-1,j);
    }else{
        printLCS(i,j-1);
    }
}
int main()
{
    cin >> s1 >> s2;
    int len1 = strlen(s1), len2 = strlen(s2);
    for(int i = 1; i <= len1; i++){
        for(int j = 1;j <= len2; j++){
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                flag[i][j] = 0;
            }else{
                if(dp[i-1][j] > dp[i][j-1]){
                    dp[i][j] = dp[i-1][j];
                    flag[i][j] = 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                    flag[i][j] = -1;
                }
            }
        }
    }
    printLCS(len1,len2);
    cout << endl;
    return 0;
}

我们需要一个数组记录每次的最大值是从哪个状态转移过来的，要输出的时候，使用递归函数，自顶向下递归，从里到外打印输出。

进阶：现在还要求出两个字符串最长公共子序列的个数有多少？https://www.luogu.com.cn/problem/P2516

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define maxn 5010
#define MOD 100000000
char A[maxn],B[maxn],cur;
int f[2][maxn], g[2][maxn];

int main()
{
    scanf("%s%s", A + 1, B + 1);
    int na = strlen(A + 1), nb = strlen(B + 1);
    A[na--] = '\0'; B[nb--] = '\0';
    cur=0;
    for(int i = 1; i <= nb; i++) g[0][i] = 1;
    g[0][0] = g[1][0] = 1;

    for(int i = 1; i <= na; i++)
    {
        cur ^= 1;
        for(int j = 1; j <= nb; j++)
        {
            if(A[i] == B[j]) 
                f[cur][j] =f[cur^1][j-1] + 1;
            else 
                f[cur][j] = max(f[cur^1][j], f[cur][j-1]);

            g[cur][j] = 0;
            if(f[cur][j] == f[cur^1][j]) 
                g[cur][j] += g[cur^1][j];
            if(f[cur][j] == f[cur][j-1]) 
                g[cur][j] += g[cur][j-1];
            if(f[cur][j] == f[cur^1][j] && f[cur][j] == f[cur][j-1] && f[cur^1][j-1] == f[cur][j])
                g[cur][j] -= g[cur^1][j-1];
            if(A[i] == B[j] && f[cur][j] == f[cur^1][j-1] + 1) 
                g[cur][j] += g[cur^1][j-1];
            if(g[cur][j] > MOD) 
                g[cur][j] %= MOD;
            if(g[cur][j] < 0) 
                g[cur][j] = (g[cur][j] % MOD) + MOD;
        }
    }
    printf("%d\n%d\n", f[cur][nb], g[cur][nb]);
    return 0;
}

4. 最长公共子串(lc)

状态转移方程：

$\tt dp[i][j]$表示str1前i个字符与str2前j个字符的最长公共子串。

5. 背包问题

参考文献：背包问题九讲，崔添翼。

5.1 0-1背包

问题描述：给定容量为 $V$ 的背包，有 $n$ 个物品，每个物品有价值 $w$、体积 $c$ 两个属性，求背包能装的物品最大价值。

求解：二维数组 $dp$，$dp[i][j]$ 表示有 $i$ 个物品，背包容量为 $j$ 的情况下，此时的背包最大价值；$dp[n][V]$即为答案

状态转移公式：

理解状态转移公式：

对于每个背包都有两种选择：装与不装（装的前提是当前容量 $j$ 能装下 $c[i]$），不装的话就是前 $i-1$ 个物品容量为 $j$ 时的价值 $dp[i][j]$；若选择装，则背包需要提前给当前物品留下 $c[i]$ 的空间。

代码实现（杭电2602号问题）：

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
#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
int t, n, V;
int dp[1005][1005], v[1005], w[1005];
int main()
{
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &V);
        // 输入n件物品的价值
        for(int i = 1; i <= n; i++){
            scanf("%d", &v[i]);
        }
        // 输入n件物品的体积
        for(int i = 1; i <= n; i++){
            scanf("%d", &w[i]);
        }
        // dp[i][j]代表了到第i个物品，背包容量为j时的最大价值
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= V; j++){
                if(j >= w[i]){
                    dp[i][j] = max(dp[i-1][j - w[i]] + v[i], dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        printf("%d\n", dp[n][V]);
    }
    return 0;
}

空间压缩：

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
#include <iostream>
#include <cstring>
#include <stdio.h>
#include<math.h>
using namespace std;
int t, n, V;
int dp[1005], v[1005], w[1005];
int main()
{
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &V);
        // 输入n件物品的价值
        for(int i = 1; i <= n; i++){
            scanf("%d", &v[i]);
        }
        memset(dp, 0, sizeof(dp));
        // 输入n件物品的体积
        for(int i = 1; i <= n; i++){
            scanf("%d", &w[i]);
        }
        // dp[j]代表背包容量为j时的最大价值
        for(int i = 1; i <= n; i++){
            for(int j = V; j >= w[i]; j--){//注意逆序
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        printf("%d\n", dp[V]);
    }
    return 0;
}

初始化的细节问题

  • 当有些问题要求“恰好装满背包”时的最优解，这时在初始化的时候，dp数组除了dp[0]为0，其余dp[1…V]均设置为无穷大。可以这样理解：初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为$0$的背包可以在什么也不装且价值为 $0$ 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为无穷大了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

  • 还有一种情况就是求背包的最小价值，把转移方程中的$max$改为$min$即可。

  • 有些题目中，只给了价值或者重量这一个数组，那么此时我们可以认为数值上价值与重量时一致的。比如只给了价值 $v$，此时01背包状态转移公式就成了：$dp[j+1] = \max(dp[j],dp[j - v[i]] + v[i]),j \in [V,v[i]]] $。

杭电1114号问题就是以上两种情况的结合。题目大意就是给定存钱罐初始重量和装满时候的重量，然后给定几种不同价值和重量的硬币，问能够恰好装满存钱罐的最小价值是多少？每个种类的硬币可以无限使用，这是一个完全背包问题。

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
#include <iostream>
#include <stdio.h>
#include <memory.h>

using namespace std;
int m, n, t, N;
int v[502], w[502]; // 硬币价值 和 硬币重量数组
int dp[10005];

const int inf = 0x3f3f3f3f;

int main()
{
    scanf("%d",&N);
    while(N--){

        //输入初始存钱罐重量和现在存钱罐重量
        scanf("%d %d", &m, &n);
        int V = n - m; // 钱币重量
        // 输入硬币种类
        scanf("%d", &t);
        for(int i = 0; i < t; i++){
            scanf("%d %d",&v[i], &w[i]);
        }
        // 注意初始化
        memset(dp, inf, sizeof(dp));
        dp[0] = 0;
        // 找到恰好能装满存钱罐重量的钱币价值中最小的那个
        for(int i = 0; i < t; i++){
            for(int j = w[i]; j <= V; j++){// 注意这是顺序
                dp[j] = min(dp[j - w[i]] + v[i], dp[j]);
            }
        }
        if(dp[V] == inf){
            printf("This is impossible.\n");
        }else{
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[V]);
        }
    }
    return 0;
}
  • Leetcode 416号问题：划分等和子集。

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

事实上这是个$NP$难问题，但在给定的数据规模下，可以转化为0-1背包问题求解。具体就是：给定n件物品，背包容量为 sum / 2 能否选择一些物品，恰好装满背包？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canPartition(int[] nums) {
        // 转为01背包问题；给定n件物品，背包容量为 sum / 2 能否选择一些物品，恰好装满背包
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        if((sum & 1) == 1){//总和为奇数，一定不可以对半分
            return false;
        }
        int target = sum / 2; // 背包容量
        int dp[] = new int[target + 1];
        for(int i = 0; i < nums.length; i++){
            for(int  j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}

5.2 完全背包

定义

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有无限件可用。放入第 $i$ 种物品的费用是 $c_i$，价值是 $w_i$。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

求解

虽然物品个数是无限的，但是实际上，由于背包容量有上限，每个物品最多选取的个数也是有限制的，这样可以转换成多重背包问题，进而可以转换成 01 背包问题。

1
2
3
4
5
6
7
for(int i = 1; i <= N; i++){
    for(int j = 0; j <= v; j++){
        for(int k = 0; k*c[i] <= j; k++){
            dp[i][j] = max(dp[i-1][j - k * c[i]] + w[i] * k, dp[i][j]);
        }
    }
}

观察状态转移公式，我们可以用$dp[i][j - c_i]$去更新$dp[i][j]$而不用去枚举$k$了，因此状态转移公式就变成：

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= N; i++){
    for(int j = 0; j <= v; j++){
        if(j >= c[i]){
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i]);
        }else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

空间压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstring>
using namespace std;
int dp[1010];
int w[21],c[21];
int main() {
    int N, V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = c[i]; j <= V; j++){ // 顺序
            dp[j] = max(dp[j- c[i]] + w[i],dp[j]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

可以看到完全背包就是在第二重循环遍历次序与01背包不同而已，01背包是逆序，完全背包是顺序。

5.3 多重背包

定义

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $n_i$ 件可用，每件耗费的空间是 $c_i$，价值是 $w_i$。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21],n[21];
int main() {
    int N,V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i] >> n[i];
    }
    for(int i =1; i <= N; i++){
        for(int j = 0; j <= V; j++){
            for(int k = 0;  k <= n[i]; k++){
                if(j >= c[i]*k){
                    dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k, dp[i][j]);
                }
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
using namespace std;
int dp[1010];
int w[21],c[21],n[21];
int main() {
    int N,V;
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> c[i] >> n[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = V; j >= 0; j--){
            for(int k = 0; k <= n[i]; k++){
                if(j >= c[i]*k){
                    dp[j] = max(dp[j - c[i]*k] + w[i] * k,dp[j]);
                }
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

多重背包的二进制优化

二进制思想即任意数字都可以由$2$的次幂的数字组合而来（用01表示），这是计算机的基础。利用这个思想，我们可以把每个物品数量分成$1,2,4,…,n - 2^K + 1$，每一组的体积和价值分别为$(c_i，w_i),(2c_i,2w_i)，(4c_i，4w_i)$，等等，通过这些组合（选择装与不装）一定可以组成$n$，这样就遍历了$1-n$内所有数字。通过拆分所有物品，就形成了一个新的价值和体积物品组，这些问题组我们可以选择装也可以选择不装，这样利用二进制优化就可以将多重背包转化为01背包问题。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 二进制优化
int ncnt = 1; // 记录新的拆分组数
for(int i = 1; i <= t; i++){ // t个物品
    // 将num[i]拆分
    for(int k = 1; k <= num[i]; k <<=1){
        nv[ncnt] = k * v[i];//新拆分的价值数组
        nw[ncnt++] = k * w[i];//新拆分的重量数组
        num[i] -= k;
    }
    if(num[i] > 0){
        nv[ncnt] = v[i] * num[i];
        nw[ncnt++] = w[i] * num[i];
    }
}
// 01背包
for(int i = 1; i < ncnt; i++){
    for(int j = V; j >= nw[i]; j--){
        dp[j] = max(dp[j - nw[i]] + nv[i], dp[j]);
    }
}

杭电1059、2844号题是完全背包的二进制优化。

5.4 有约束的背包问题

杭电3466号问题。题目大意是说，给定背包容量，每个物品的重量$P$，若要装入该物品要求的最小背包容量$Q$以及该物品的价值$V$，输出不超过背包容量下所能获取的最大物品价值。

相比于裸01背包，这个题目要求装入的时候必须考虑$P,Q$这两个条件，要用到贪心。即$A$物品$p_1=3,q_1=5$，$B$物品$p_2=4,q_2=3$；背包容量为$7$，若先装$A$，所需容量至少为$p_1 + q_2 = 7$，若先装$B$，所需容量至少为$p_2 + q_1 = 9$，因此应该选择容量小的。即：$p_1 + q_2 < p_2 + q_1 \rightarrow q_1-p_1 > q_2 - p_2$，即$q-p$大的先买。但是转移方程中，更新过程是逆向的，因此排序的时候应该按照$p-q$从小到大排序。

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
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
int n, V, dp[5005];
struct item{
    int p,q,v;
}items[5005];
bool cmp(struct item a, struct item b){
    return a.q - a.p < b.q - b.p; // 按照 q-p 从小到大排序
}
int main()
{
    while(~scanf("%d %d",&n,&V)){
        for(int i = 1; i <= n; i++){
            // p就是物品的重量 v是物品的价值， 背包容量必须大于p和q才能装入
            scanf("%d %d %d", &items[i].p, &items[i].q, &items[i].v);
        }
        sort(items + 1, items + 1 + n, cmp);
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++){
            for(int j = V; j >= max(items[i].p, items[i].q); j--){
                dp[j] = max(dp[j], dp[j - items[i].p] + items[i].v);
            }
        }
        printf("%d\n",dp[V]);
    }
    return 0;
}

背包练习(以下题目皆来自杭电 on-line judge: http://acm.hdu.edu.cn/ ，做完还不会背包来找我。

2602 1114 1171 2844 1059 2955 1203 3466

6. 编辑距离

问题描述：

给你两个单词word1和word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

视频讲解：https://www.youtube.com/watch?v=MiqoA-yF-0M

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
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        int[][] dp = new int[n + 1][m + 1];

        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }

        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= m; j++) {
                // 前三种情况
                dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1));
                // 第四种情况
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}

7. 区间DP

概述：区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来由很大的关系。令状态 $f(i,j)$ 表示将下标位置 $i$ 到 $j$ 的所有元素合并能获得的价值的最大（最小）值，那么 $f(i,j) = \max\{f(i,k) + f(k+1,j) + cost\}$，$cost$ 为将这两组元素合并起来的代价。

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

7.1 矩阵相乘的最少次数

https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_B

本质上是在填一张表。

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
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n;

struct matrix{
    int row, col;
}matrices[105];
int main()
{
    while(cin >> n){
        int dp[105][105];
        for(int i = 1; i <= n; i++){
            cin >> matrices[i].row >> matrices[i].col;
        }
        //填表：自左向右，自下而上 只要填写上半部分
        // dp[i,j] = min{dp[i:k] + dp[k+1:j] + row_i * p * col_j} i <= k < j
        for(int i = 1; i <= n; i++){//从左到右
            for(int j = i; j > 0; j--){//自下而上
                if(i == j){// 对角线元素 dp[i][i] = 0
                    dp[i][j] = 0;
                }else if(i - j == 1){
                    // i矩阵与j矩阵相乘：
                    dp[j][i] = matrices[j].row * matrices[j].col * matrices[i].col;
                }else{
                    dp[j][i] = 2 << 20;
                    for(int k = j; k < i; k++){
                        int t = matrices[j].row * matrices[k].col * matrices[i].col;
                        dp[j][i] = min(dp[j][k] + dp[k+1][i] + t,dp[j][i]);
                    }
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    return 0;
}

7.2 石子合并

https://vjudge.net/problem/51Nod-1021

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 205;
const int INF = 2 << 21;
// dp[i][j]表示区间[i,j]所能形成的最优答案
int n, nums[maxn], dp[maxn][maxn], sum[maxn];
int main()
{
    cin >> n;
    int tmp = 0;
    for(int i = 1; i <= n; i++){
        cin >> nums[i];
        tmp += nums[i];
        sum[i] = tmp;
    }

    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            dp[i][j] = INF;
        }
    }
    for(int len = 1; len <= n; len++){//枚举区间长度
        for(int i = 1; i + len - 1 <= n; i++){//枚举区间起点
            int j = i + len - 1;//区间终点
            for(int k = i; k <= j; k++){//枚举分割点
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

7.3 Dire Wolf

杭电：http://acm.hdu.edu.cn/showproblem.php?pid=5115

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n, t, a[205], b[205], dp[205][205];
const int INF = 2 << 25;
int main(){
    /**
    dp[i][j] 代表 i 到 j的狼被杀死 所受的最小伤害，结果就是dp[0][n-1]
    当 1 < i < t ,每条狼的攻击力 a[i] + b[i-1] + b[i+1]
    当这只狼被打败，那么他给邻接的狼提供的攻击力会失效
    考虑没有附加攻击的情况，无论怎么打都是所有a求和，
    现在添加了b，本质上是要我们选择使附加攻击最小的一种方案。
    通过样例我们可以总结出来如果有附带伤害高的狼先杀他，
    然后尽量杀两端的狼，这样只有一边有附带伤害
    */
    while(cin >> n){
        for(int cnt = 0; cnt < n; cnt++){
            cin >> t;
            memset(a, 0, sizeof(a));
            memset(b, 0, sizeof(b));
            for(int i = 1; i <= t; i++){
                cin >> a[i];
            }
            for(int i = 1; i <= t; i++){
                cin >> b[i];
            }
            memset(dp,0,sizeof(dp));
            for(int i = 1;i <= t; i++){
                for(int j = i; j <= t; j++){
                    dp[i][j] = INF;
                }
            }

            for(int len = 1; len <= t; len++){// 枚举区间长度
                for(int i = 1; i + len - 1 <= t; i++){//枚举区间起点
                    int j = i + len - 1;//终点
                    for(int k = i; k <= j; k++){//枚举分割点
                        dp[i][j] = min(dp[i][j],dp[i][k-1] + dp[k+1][j] + a[k] + b[i-1] + b[j+1]);
                    }
                }
            }
            printf("Case #%d: %d\n",cnt+1,dp[1][t]);
        }
    }
    return 0;
}

7.4 Brackets

题目链接：https://vjudge.net/problem/POJ-2955

状态转移方程：当s[i]='(' \ and\ s[j]==')'\ or\ s[i]='[' \ and\ s[j]==']' 时，dp[i][j] = dp[i+1][j-1] + 2;还有就是dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);。

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char ch[105];
int dp[105][105];//表示区间dp[i][j]表示[i,j]内的最大匹配数

int main()
{
    while(cin >> ch && strcmp(ch,"end")!= 0){
        int len = strlen(ch);
        memset(dp, 0, sizeof(dp));

        for(int t = 2; t <= len; t++){//枚举区间长度
            for(int i = 0; i + t - 1 < len; i++){//枚举区间起点
                int j = i + t - 1;//区间终点
                if((ch[i] == '(' && ch[j] == ')') || (ch[i] == '[' && ch[j] == ']')){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                for(int k = i; k <= j; k++){
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
        cout << dp[0][len-1] << endl;
    }
    return 0;
}

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true