动态规划

背包问题算法模板

动态规划之背包问题

Posted by WenlSun" on April 28, 2020

0-1背包问题

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。 第 $i$ 件物品的体积是 $v_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
24
25

#include <iostream>

using namespace std;

const int N = 10010;

int n, m;
int v[N], w[N];
int dp[N][N]; // dp[i][j]表示只看前i个物品，在总体积为j的情况下，总价值最大是多少

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[n][m] << endl;
}

优化版本

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>

using namespace std;

const int N = 10010;

int n, m;
int v[N], w[N];
int dp[N];

int main() {
    cin >> n >> m;
    // 初级
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;

    // 终极
    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[m] << endl;
}

完全背包问题

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。 第 $i$ 种物品的体积是 $v_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
24
25

#include <iostream>

using namespace std;

const int N = 10010;

int n, m;
int v[N], w[N];
int dp[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        }
    }
    cout<< dp[n][m] << endl;
}

优化版本

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>

using namespace std;

const int N = 10010;

int n, m;
int v[N], w[N];
int dp[N];

int main() {
    cin >> n >> m;
    // 初级
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout<< dp[m] << endl;

    // 终极
    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout<< dp[m] << endl;
}

多重背包问题I(扩展的0-1背包问题)

有 $N$ 种物品和一个容量是 $V$ 的背包。 第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_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
24
25
26
27

#include <iostream>

using namespace std;

/**
 * 时间复杂度：O(n^3)
 */

const int N = 110;
int n, m;
int dp[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= s; k++) {
                if (j >= k * v)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v] + k * w);
            }
        }
    }
    cout << dp[n][m] << endl;
}

优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>

using namespace std;

const int N = 110;
int n, m;
int dp[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >=0; j--) {
            for (int k = 1; k <= s&& k * v <= j; k++) {
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
            }
        }
    }
    cout << dp[m] << endl;
}

多重背包问题II

有 $N$ 种物品和一个容量是 $V$ 的背包。 第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。原题链接

数据范围:
$0\le N \leq 1000$
$0\le V \leq 2000$
$0\le v_i,w_i,s_i \leq 2000$

思路：考虑如何将一个多重背包问题转换成0-1背包问题，也就是将有$s_i$件物品的拆分成s件相同的物品，然后放到物品组当中去.
多重背包问题的二进制优化方法
给定一个数s，从小于等于s的数中最少选多少个数字可以组合出小于等于s的所有数字，在组合的时候，选出来的数字有两种操作，在组合时被选，或者不被选。如：7 （1，2，4）；10 （1，2，4，3）。
结论：至少需要$\lceil log_2(s)\rceil$个数字。这些数字是2的整次幂和用s减2的整次幂到不能减时(再减就成负数了)的数字。

1
2
3
4
5
6

vector<int> res;
for(int i = 1; i <= s; i *= 2){
    res.push_back(i);
    s -= i;
}
if (s > 0) res.push_back(s);

参考代码

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

using namespace std;

/**
 * 时间复杂度：O(n^2)
 */

const int N = 2010;

int n, m;
int dp[N];

struct Good {
    int v, w;  // 物品的体积和价值
};

int main() {
    cin >> n >> m;
    vector<Good> goods;
    for (int i = 0; i < n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        // 转换成0-1背包问题
        for (int k = 1; k <= s; k *= 2) {
            s -= k;
            goods.push_back({k * v, k * w});
        }
        if (s > 0) goods.push_back({s * v, s * w});
    }
    // 套用0-1背包问题模板
    for (auto g : goods) {
        for (int j = m; j >= g.v; j--) {
            dp[j] = max(dp[j], dp[j - g.v] + g.w);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

多重背包问题III

有 $N$ 种物品和一个容量是 $V$ 的背包。 第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。原题链接

数据范围:
$0\le N \leq 1000$
$0\le V \leq 20000$
$0\le v_i,w_i,s_i \leq 20000$

思路：

参考代码

1

待填。。。

混合背包问题

有 $N$ 种物品和一个容量是 $V$ 的背包。
物品一共有三类：
第一类物品只能用1次（0-1背包）s = -1；
第二类物品可以用无限次（完全背包）s = 0；
第三类物品最多只能用 $s_i$ 次（多重背包）s > 0；
每种体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值.原题链接

思路：将多重背包问题先利用二进制优化转换为0-1背包，然后物品就有两种类型，0-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

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int dp[N];

struct Good {
    int kind;  //物品类型
    int v, w;  // 体积和价值
};

int main() {
    cin >> n >> m;
    vector<Good> goods;
    for (int i = 0; i < n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s < 0)
            // 0-1背包
            goods.push_back({-1, v, w});
        else if (s == 0)
            // 完全背包
            goods.push_back({0, v, w});
        else {
            // 多重背包转0-1 背包
            for (int k = 1; k <= s; k *= 2) {
                s -= k;
                goods.push_back({-1, k * v, k * w});
            }
            if (s > 0) goods.push_back({-1, s * v, s * w});
        }
    }
    // 先遍历所有的物品
    for (auto g : goods) {
        if (g.kind < 0) {
            // 0-1背包问题
            for (int j = m; j >= g.v; j--)
                dp[j] = max(dp[j], dp[j - g.v] + g.w);
        } else {
            // 完全背包问题
            for (int j = g.v; j <= m; j++)
                dp[j] = max(dp[j], dp[j - g.v] + g.w);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

二维费用的背包问题

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。原题链接

思路：在0-1背包问题的基础上多了一层重量的循环

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, g;   // 数量，体积，重量
int dp[N][N];  // dp[i][j]表示总体积不超过i，总重量不超过j时的最大价值

int main() {
    cin >> n >> m >> g;
    for (int i = 0; i < n; i++) {
        int v, w, p;  // 体积，重量, 价值
        cin >> v >> w >> p;
        for (int j = m; j >= v; j--) { // 体积
            for (int k = g; k >= w; k--) { // 重量
                dp[j][k] = max(dp[j][k], dp[j - v][k - w] + p);
            }
        }
    }
    cout << dp[m][g] << endl;
    return 0;
}

分组背包问题

有 $N$ 组物品和一个容量是 $V$ 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。原题链接

思路：0-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

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
// v[i][k] 表示第i组中第k个物品的体积
// w[i][k] 表示第i组中第k个物品的价值
// s[i] 表示第i组的物品数量
int v[N][N], w[N][N], s[N];
int dp[N][N];

int main() {
    cin >> n >> m;  // n组物品，m的容量
    for (int i = 1; i <= n; i++) {
        cin >> s[i];  // 每组物品的数量
        for (int j = 0; j < s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            // 这儿有k种选择
            for (int k = 0; k < s[i]; k++) {
                if (j >= v[i][k])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    cout << dp[n][m] << endl;
}

优化版本

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

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
// v[i][k] 表示第i组中第k个物品的体积
// w[i][k] 表示第i组中第k个物品的价值
// s[i] 表示第i组的物品数量
int v[N][N], w[N][N], s[N];
int dp[N];

int main() {
    cin >> n >> m;  // n组物品，m的容量
    for (int i = 1; i <= n; i++) {
        cin >> s[i];  // 每组物品的数量
        for (int j = 0; j < s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 0; j--) {
            for (int k = 0; k < s[i]; k++) {
                if (j >= v[i][k])
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
            }
        }
    }
    cout << dp[m] << endl;
}

背包问题求方案数

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 最优选法的方案数。注意答案可能很大，请输出答案模 $10^9+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

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, mod = 1e9 + 7, INF = 100000000;

int n, m;
// dp[j] 表示当体积恰好是j的时候的最大价值，g[j]表示体积恰好是j的时候的方案数。
int dp[N], g[N];

int main() {
    cin >> n >> m;
    g[0] = 1;  // 体积为0时的方案数只有一种
    for (int i = 1; i <= m; i++) dp[i] = -INF;  // 这儿区别于0-1背包问题
    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--) {
            // 这儿计算最大值价值，分两种情况
            int t = max(dp[j], dp[j - v] + w);
            int s = 0;
            // 如果和第一种情况相同，加第一种对应的方案数
            if (t == dp[j]) s += g[j];
            // 如果和第二种情况相同，加第二种对应的方案数
            if (t == dp[j - v] + w) s += g[j - v];
            if (s >= mod) s -= mod;
            dp[j] = t;
            g[j] = s;
        }
    }
    int maxw = 0;
    // 寻找最大价值(并不一定体积用满才是最优方案)，区别于0-1背包问题中动态数组的含义！！！
    for (int i = 0; i <= m; i++) maxw = max(maxw, dp[i]);
    int res = 0;
    for (int i = 0; i <= m; i++) {
        if (dp[i] == maxw) res += g[i];
        if (res >= mod) res -= mod;
    }
    cout << res << endl;
    return 0;
}

背包问题求具体方案

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。原题链接

思路：注意只能用二维的动态数组，通过判断dp[n-1][m]是否等于dp[n][m]来判断第n个物品有没有被选。

参考代码

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

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
// 通过判断dp[n-1][m]是否等于dp[n][m]来判断第n个物品有没有被选。
int dp[N][N];  // 这儿只能用二维

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    // 二维动态数组的时候怎么遍历都行，为了获得字典序最小的，从n开始遍历
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
        }
    }
    int vol = m;
    // 求具体方案
    for (int i = 1; i <= n; i++) {
        if (vol >= v[i] && dp[i][vol] == dp[i + 1][vol - v[i]] + w[i]) {
            cout << i << ' ';
            vol -= v[i];
        }
    }
    return 0;
}

有依赖的背包问题

有 $N$ 个物品和一个容量是 $V$ 的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。每件物品的编号是 $i$，体积是 $v_i$，价值是 $w_i$，依赖的父节点编号是 $p_i$。物品的下标范围是 1…N。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。原题链接

思路：树形dp + 分组背包问题 (没看懂。。。)

参考代码

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

using namespace std;

const int N = 110;

int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N], dp[N][N];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

void dfs(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int son = e[i];
        dfs(son);
        for (int j = m - v[u]; j >= 0; j--) {
            for (int k = 0; k <= j; k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
            }
        }
    }
    for (int i = m; i >= v[u]; i--) dp[u][i] = dp[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i++) dp[u][i] = 0;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int root;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1)
            root = i;
        else
            add(p, i);
    }
    dfs(root);
    cout << dp[root][m] << endl;
    return 0;
}

一和零(中等)

在计算机界中，我们总是追求用有限的资源获取最大的收益。现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 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

class Solution {
   public:
    /**
     * 转换为0-1背包问题
     */
    typedef pair<int, int> PII;
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (auto s : strs) { // 枚举每一个物品
            PII t;
            cnt(s, t); // 计算物品的每一部分（0和1）的体积(数量)
            // 0-1背包问题的模板 这儿的背包容量是二维的
            for (int i = m; i >= t.first; i--) {
                for (int j = n; j >= t.second; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - t.first][j - t.second] + 1);
                }
            }
        }
        return dp[m][n];
    }
    // 统计当前物品的容量
    void cnt(string& s, PII& t) {
        int n0 = 0, n1 = 0;
        for (auto c : s) {
            if (c == '0')
                n0++;
            else
                n1++;
        }
        t.first = n0, t.second = n1;
    }
};
FEATURED TAGS
笔记 算法 Object Detection 算法模板 pytorch 笔经 动态规划 面经 面试题 C++ Vim
FRIENDS