DDqiuqiu
0%

动态规划

Posted on Edited on

本文主要以01背包，最长共子序列，最大子数组和等问题讲解动态规划。

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
#include <bits/stdc++.h>

using namespace std;

void knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 初始化G表追踪状态，0表示未选，1表示选了
    vector<vector<bool>> selected(n + 1, vector<bool>(cap + 1, false));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
                // 选取状态更新
                if (dp[i][c] == dp[i - 1][c - wgt[i - 1]] + val[i - 1]) {
                    selected[i][c] = true;
                }
            }
        }
    }
    // 最大数值
    cout << dp[n][cap] << endl;
    // 打印最优方案
    vector<int> selectedItems;
    int i = n, c = cap;
    while (i > 0 && c > 0) {
        if (selected[i][c]) {
            selectedItems.push_back(i - 1); // 保存选中的物品索引
            c -= wgt[i - 1];
        }
        i--;
    }
    for (int j = selectedItems.size() - 1; j >= 0; j--) {
        cout << "x" << selectedItems[j] + 1 << " ";
    }
    cout << endl;

    return;
}

int main() {
    // 物品数量
    int n;
    // 背包限制
    int cap;
    // 数据输入
    cin >> n >> cap;

    // 长度数组，重量数组
    vector<int> wgt(n);
    vector<int> val(n);
    // 数组输入
    for (int i = 0; i < n; i++) {
        cin >> wgt[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> val[i];
    }

    // 结果计算
    knapsackDP(wgt, val, cap);

    return 0;
}

对于这段代码，在通过一个数据集时，输出为

1
2
42
x1 x3 x4 x6 x8 x9 x10

然而期望输出为

分析原因，并修改代码

1
2
42
x1 x3 x4 x6 x7 x8 x10

在你的代码中，当你在追踪选取状态时，可能出现错误。在选取状态更新部分，你使用了：

1
2
3
if (dp[i][c] == dp[i - 1][c - wgt[i - 1]] + val[i - 1]) {
    selected[i][c] = true;
}

这样的判断条件会导致在选择物品 i 时，只能考虑到上一行的状态，而忽略了之前已经选择的物品对当前状态的影响。这就是为什么你的输出结果与期望输出不同的原因。

修改的方法是，在状态转移时，考虑前一次迭代的状态，而不仅仅是上一行的状态。这样可以确保在更新选取状态时，考虑到之前已经选择的物品对当前状态的影响。

下面是修改后的代码：

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
#include <bits/stdc++.h>

using namespace std;

void knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 初始化G表追踪状态，0表示未选，1表示选了
    vector<vector<bool>> selected(n + 1, vector<bool>(cap + 1, false));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
                // 选取状态更新
                if (dp[i][c] == dp[i - 1][c]) {
                    selected[i][c] = false; // 不选物品 i
                } else {
                    selected[i][c] = true; // 选物品 i
                }
            }
        }
    }
    // 最大数值
    cout << dp[n][cap] << endl;
    // 打印最优方案
    vector<int> selectedItems;
    int i = n, c = cap;
    while (i > 0 && c > 0) {
        if (selected[i][c]) {
            selectedItems.push_back(i - 1); // 保存选中的物品索引
            c -= wgt[i - 1];
        }
        i--;
    }
    for (int j = selectedItems.size() - 1; j >= 0; j--) {
        cout << "x" << selectedItems[j] + 1 << " ";
    }
    cout << endl;

    return;
}

int main() {
    // 物品数量
    int n;
    // 背包限制
    int cap;
    // 数据输入
    cin >> n >> cap;

    // 长度数组，重量数组
    vector<int> wgt(n);
    vector<int> val(n);
    // 数组输入
    for (int i = 0; i < n; i++) {
        cin >> wgt[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> val[i];
    }

    // 结果计算
    knapsackDP(wgt, val, cap);

    return 0;
}

这样的修改应该会使你的代码输出期望的结果。