动态规划专题——背包模型
liyusendesu
|
ALGORITHM,Intermediate Algorithm
|
|
1,659
|
0

11214 字
|
1.6 小时
本文最后更新于 839 天前，其中的信息可能已经有所发展或是发生改变。

1. 01背包问题

1.1 模板题

01背包问题

原题链接

描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

4 5
1 2
2 4
3 4
4 5

输出样例：

输出样例：

8

思想

  • 状态表示：
    • 集合：dp[i][j]表示前i个物品，总体积不超过j的价值
    • 属性：最大价值
  • 状态计算：
    • 不选第i个 物品：dp[i][j] = dp[i - 1][j]
    • 选第i个物品：dp[i][j] = dp[i - 1][j - v[i]] + w[i]
    • 集合属性为最大价值，故两种情况取max()
  • 当背包容量不够，即j < v[i]时，不能选择物品，反之可选

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N][N];

int v[N], w[N];

void solve(){

    int n, m;

    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];  //不选物品i
            if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);  //选择物品i
        }
    }

    cout << dp[n][m] << endl;

}

int main(){

    solve();

    return 0;

}

优化

  • 对于dp[i][j]记录了全部的i个物品在j容量下的最大价值，但我们只需要dp[n][m]，故只需要dp[j]
  • 对于dp[i][j]的更新，dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i])，当第一维的i被省略后，更新时会产生歧义
  • 故更新dp[j]需要从j = m到j = v[i]逆序，避免歧义
  • 状态表示：
    • 集合：dp[j]为$N$件物品，容量为j的价值
    • 属性：最大价值
  • 状态计算：
    • dp[j] = max(dp[j],dp[j - v[i]] + w[i])

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N];

int v[N], w[N];

void solve(){

    int n, m;

    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;

}

int main(){

    solve();

    return 0;

}

1.2 提高练习

426. 开心的金明

原题链接

描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。

于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。

他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 

设第 j 件物品的价格为 v[j]，重要度为 w[j]，共选中了 k 件物品，编号依次为 j1，j2，…，jk，则所求的总和为： 

v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]
请你帮助金明设计一个满足要求的购物单。

输入格式
输入文件的第 1 行，为两个正整数 N 和 m，用一个空格隔开。（其中 N 表示总钱数，m 为希望购买物品的个数） 

从第 2 行到第 m+1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v 和 p。（其中 v 表示该物品的价格，p 表示该物品的重要度）

输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 108）。

数据范围
1≤N<30000,
1≤m<25,
0≤v≤10000,
1≤p≤5
输入样例：

1000 5
800 2
400 5
300 5
400 3
200 2

输出样例：

3900

思想

  • 01背包模板题
  • 将优先度和花费的乘积视为价值

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int dp[N];

int v[N], w[N];

void solve(){

    int n, m;

    cin >> m >> n;

    for(int i = 1; i <= n; i ++){
        cin >> v[i] >> w[i];
        w[i] *= v[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;
}

int main(){

    solve();

    return 0;

}

1024. 装箱问题

原题链接

描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式
第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式
一个整数，表示箱子剩余空间。

数据范围
0<V≤20000,
0<n≤30
输入样例：

24
6
8
3
12
7
9
7

输出样例：

0

思想

  • 将物品的价值视为与体积相等，转化为01背包问题
  • 即选择物品附带的价值等于选择物品占用的体积
  • 状态表示：
    • 集合：dp[j]表示体积不超过j时，已使用的体积
    • 属性：最大使用体积
  • 状态计算：
    • dp[j] = max(dp[j],dp[j - v[i]] + v[i])

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int dp[N];

int v[N];

void solve(){

    int n, m;
    cin >> m >> n;

    for(int i = 1; i <= n; i ++) cin >> v[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]] + v[i]);
        }
    }

    cout << m - dp[m] << endl;

}

int main(){

    solve();

    return 0;

}

278. 数字组合

原题链接

描述

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入格式
第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示 A1,A2,…,AN。

输出格式
包含一个整数，表示可选方案数。

数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2

输出样例：

3

思想

  • 状态表示：
    • 集合：dp[i][j]表示前i个数选择的数之和恰好等于j的集合
    • 属性：集合的个数
  • 状态计算：
    • 不选第i个数：dp[i][j] = dp[i][j]
    • 选第i个数：dp[i][j] = dp[i - 1][j - v[i]]
    • 初始化：dp[0][0] = 1，j = 0时不选即为一种方案
    • 集合属性为集合的个数，取两种方案之和：dp[i][j] += dp[i - 1][j - v[i]]
    • 优化：dp[j] += dp[j - v[i]]

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;

int dp[N];

int v[N];

void solve(){

    int n, m;

    cin >> n >> m;

    dp[0] = 1;

    for(int i = 1; i <= n; i ++){
        cin >> v[i];
    }

    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= v[i]; j --){
            dp[j] += dp[j - v[i]];
        }
    }

    cout << dp[m] << endl;

}

int main(){

    solve();

    return 0;

}

734. 能量石

原题链接

描述

岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N 块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为 Si 秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含 Ei 单位的能量，并且每秒将失去 Li 单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至 0。

请问杜达通过吃能量石可以获得的最大能量是多少？

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N，表示能量石的数量。

接下来 N 行，每行包含三个整数 Si,Ei,Li。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 是组别编号（从 1 开始），y 是可以获得的最大能量值。

数据范围
1≤T≤10,
1≤N≤100,
1≤Si≤100,
1≤Ei≤105,
0≤Li≤105
输入样例：

3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0

输出样例：

Case #1: 105
Case #2: 8
Case #3: 500

思想

  • 贪心 + 01背包

  • 对于两个相邻的能量石$i,j$

  • E_i+E_j−S_i×L_j \ge E_j+E_i−S_j×L_i\\\\ S_j×L_i\ge S_i×L_j

  • 于是对于最优解中所有$S_j×L_i \lt S_i×L_j$的物品次序，我们都可以通过一次邻项交换的操作变成我们上述的次序，且保证该次交换完成后，总价值不减少

代码

#include <bits/stdc++.h>
using namespace std;

int _, __;

const int N = 110;

struct point{
    int s, e, l;
    bool operator < (const point &p) const{
        return s * p.l < p.s * l;
    }
};

void solve(){

    int dp[N * N] = {0};

    point p[N];

    int n;

    cin >> n;

    int m = 0;

    for(int i = 1; i <= n; i++) {
        cin >> p[i].s >> p[i].e >> p[i].l;
        m += p[i].s;
    }

    sort(p + 1, p + 1 + n);

    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= p[i].s; j--){
            dp[j] = max(dp[j], dp[j - p[i].s] + max(0, p[i].e - (j - p[i].s) * p[i].l));
        }
    }

    int res = 0;

    for(int i = 1; i <= m; i++) res = max(res, dp[i]);

    printf("Case #%d: %d\n", __, res);

}

int main(){

    int _;

    cin >> _;

    for(__ = 1; __ <= _; __ ++){
        solve();
    }

    return 0;

}

2. 完全背包问题

2.1 模板题

完全背包问题

原题链接

描述

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

4 5
1 2
2 4
3 4
4 5

输出样例：

输出样例：

10

思想

  • 状态表示：
    • 集合：dp[i][j]表示前i个物品，总体积不超过j的价值
    • 属性：最大价值
  • 状态计算：
    • 不选第i个 物品：dp[i][j] = dp[i - 1][j]
    • 选第i个物品共k个：dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i]
    • 集合属性为最大价值，故两种情况取max()
  • 当背包容量不够，即j < k * v[i]时，不能选择物品，反之可选

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 +3;

int dp[N][N];

int v[N], w[N];

void solve(){

    int n, m;

    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 ++){
            for(int k = 0; k * v[i] <= j; k ++){
                dp[i][j] = max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << dp[n][m] << endl;

}

int main(){

    solve();

    return 0;

}

优化

  • dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i], dp[i - 1][j - 3 * v[i]] + 3 * w[i], ...)
  • dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2 * v[i]] + w[i], dp[i - 1][j - 3 * v[i]] + 2 * w[i], ...)
  • 即dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])，与k取值无关
  • 由此k层循环可以被优化掉
  • 进一步优化，发现更新方式同01背包：
    • 01背包：dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i])
    • 完全背包：dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i])
  • 即可将dp[i][j]的第一维按01背包的思想将其优化：dp[j] = max(dp[j],dp[j - v[i]] + w[i])
  • 由于更新时i不会产生歧义，故不需要逆序更新，顺序更新即可

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N];

int v[N], w[N];

void solve(){

    int n, m;

    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;

}

int main(){

    solve();

    return 0;

}

2.2 提高练习

1023. 买书

原题链接

描述

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式
一个整数 n，代表总共钱数。

输出格式
一个整数，代表选择方案种数。

数据范围
0≤n≤1000

20

输出样例：

输出样例：

2

思想

  • 书的数量不限，转化为完全背包问题

  • 状态表示：

    • 集合：dp[i][j]表示前i种书，选择的价格恰好等于j的集合
    • 属性：集合的个数

  • 状态计算：

    • 不选第i种书：dp[i][j] = dp[i - 1][j]
    • 选第i种书共k本：dp[i][j] = dp[i - 1][j - k * v[i]]
    • 集合属性为集合的个数，取两种方案之和：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - k * v[i]]

  • 当背包容量不够，即j < k * v[i]时，不能选择书，反之可选

  • 优化状态计算：dp[j] += dp[j - v[i]]

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int dp[N];

int v[N] = {0, 10, 20, 50, 100};

void solve(){

    int m;

    cin >> m;

    dp[0] = 1;

    for(int i = 1; i <= 4; i ++){
        for(int j = v[i]; j <= m; j ++){
            dp[j] += dp[j - v[i]];
        }
    }

    cout << dp[m] << endl;

}

int main(){

    solve();

    return 0;

}

1021. 货币系统 I

原题链接

描述

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式
第一行，包含两个整数n和m。

接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
n≤15,m≤3000
输入样例：

3 10
1
2
5

输出样例：

10

思想

  • 货币的数量不限，转化为完全背包问题

  • 状态表示：

    • 集合：dp[i][j]表示前i种货币，选择的面值恰好等于j的集合
    • 属性：集合的个数

  • 状态计算：

    • 不选第i种货币：dp[i][j] = dp[i - 1][j]
    • 选第i种货币共k个：dp[i][j] = dp[i - 1][j - k * v[i]]
    • 集合属性为集合的个数，取两种方案之和：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - k * v[i]]

  • 当背包容量不够，即j < k * v[i]时，不能选择货币，反之可选

  • 优化状态计算：dp[j] += dp[j - v[i]]

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL N = 1e6 + 3;

LL dp[N];

LL v[N];

void solve(){

    LL n, m;
    cin >> n >> m;

    dp[0] = 1;

    for(LL i = 1; i <= n; i ++) cin >> v[i];

    for(LL i = 1; i <= n; i ++){
        for(LL j = v[i]; j <= m; j ++){
            dp[j] += dp[j - v[i]];
        }
    }

    cout  << dp[m] << endl;

}

int main(){

    solve();

    return 0;

}

532. 货币系统 II

原题链接

描述

有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。 

在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。

然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。

例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。 

两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。

他们希望你来协助完成这个艰巨的任务：找到最小的 m。

输入格式
输入文件的第一行包含一个整数 T，表示数据的组数。

接下来按照如下格式分别给出 T 组数据。 

每组数据的第一行包含一个正整数 n。

接下来一行包含 n 个由空格隔开的正整数 a[i]。

输出格式
输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。

数据范围
1≤n≤100,
1≤a[i]≤25000,
1≤T≤20
输入样例：

2 
4 
3 19 10 6 
5 
11 29 13 19 17

输出样例：

2
5

思想

  • $n$种货币，每种货币可以使用无穷多个，转化为完全背包
  • 对于系统$b$，其用来表示系统$a$的货币数量$m$，必然满足$m\le n$
  • 故我们对$a$进行消减，将$a_i$可以被其他若干$a_j,a_k,\dots,a_n(a_j\lt a_k\lt\dots\lt a_n\lt a_i)$表示的$a_i$消去，最终剩余的$a_i$即为新的货币系统$b$
  • 状态表示：
    • 集合：dp[i][j]表示前i个数，数值为j的方案
    • 属性：该方案是否出现过
  • 状态计算：
    • vis[N]记录出现过的方案数，cnt记录选择的最小数量
    • 当dp[i,vis[i]] == 0说明该方案未曾出现，则cnt ++
    • 不选择该方案：dp[i][j] = dp[i - 1][j]
    • 选则该方案：dp[i][j] = dp[i][j - vis[i]]
    • 集合属性为该方案是否出现过，取两种方案之和：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - vis[i]]
    • 优化：dp[j] += dp[j - vis[i]]

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;

int vis[N];

bool dp[N];

void solve(){

    memset(dp, 0, sizeof dp);

    int n;

    cin >> n;

    for(int i = 0; i < n; i ++) cin >> vis[i];

    sort(vis, vis + n);

    int maxn = vis[n - 1];

    int cnt = 0;

    dp[0] = 1;

    for(int i = 0; i < n; i ++){
        if(!dp[vis[i]]) cnt ++;

        for(int j = vis[i]; j <= maxn; j ++){
            dp[j] += dp[j - vis[i]];
        }
    }

    cout << cnt << endl;

}

int main(){

    int _;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

3. 多重背包问题

3.1 模板题

多重背包问题 I

原题链接

描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<vi,wi,si≤100

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

输出样例：

10

思想

  • 状态表示：
    • 集合：dp[i][j]表示前i个物品，总体积不超过j的价值
    • 属性：最大价值
  • 状态计算：
    • 不选第i个 物品：dp[i][j] = dp[i - 1][j]
    • 选第i个物品k个：dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i]
    • 集合属性为最大价值，故两种情况取max()
  • 当背包容量不够或者物品数量不够时，即j < k * v[i] || k > s[i]时，不能选择物品，反之可选

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N][N];

int v[N], w[N], s[N];

void solve(){

    int n, m;

    cin >> n >>m;

    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            for(int k = 0; k * v[i] <= j && k <= s[i]; k ++){  //枚举选择物品的个数
                dp[i][j] = max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << dp[n][m] << endl;

}

int main(){

    solve();

    return 0;

}

多重背包问题 II

原题链接

描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

输出样例：

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

思想

  • 由于$S$范围大，不可能逐一枚举，故采用二进制优化
  • 对于一组数$1,2,4,8,16,32$，每个数只使用一次，可以凑成如下的数：
    • 用$1,2$可以凑出$3$，即$1,2$可凑出$1\sim 3$之间的任意数
    • 则用$1,2,4$可以凑出$1\sim 7$之间的任意数
    • 则$1,2,4,8$可以凑出$1\sim 15$之间的任意数
    • 则$1,2,4,8,16$可以凑出$1\sim 31$之间的任意数
    • 则$1,2,4,8,16,32$可以凑出$1\sim 63$之间的任意数
    • 综上，使用$2^0,2^1,2^2,\dots,2^n$可以凑出$1\sim 2^{n+1}-1$之间的任意整数
  • 对于一个数$17$，若要用上述方法凑出$1\sim 17$之间的任意数：
    • 可选$1,2,4,8$，每个数只用一次即可凑出$1\sim 15$
    • 由于最大只能凑到$15$，故需添加一个数$2(17-15)$，来凑到$17$
    • 即用$1,2,4,8,2$即可凑出$1\sim 17$之间的任意一个数
  • 对于第i个物品，体积为v[i]，价值为w[i]，共有s[i]件
  • 由二进制优化，我们可以将s[i]利用二进制拆分，用$1,2,4,\dots$凑出s[i]
  • 即我们将物品i，拆分成了：
    • 一件体积为1 * v[i]的物品，价值为1 * w[i]的捆绑物品
    • 一件体积为2 * v[i]的物品，价值为2 * w[i]的捆绑物品
    • 一件体积为4 * v[i]的物品，价值为4 * w[i]的捆绑物品
    • $\dots$
  • 由拆分出的这些新的捆绑物品，我们可以凑出$1\sim s[i]$之间的任意数目的i物品，不必逐一枚举进行选择
  • 由二进制拆分，原有的每个物品数量$S$可以降为$log_2^S$，时间复杂度大幅降低
  • 对于最终求解，可以采用01背包的一维优化求解

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int dp[N];

int cnt;  //用于记录新的捆绑物品的下标

int v[N], w[N];

void solve(){

    int n, m;
    cin >> n >> m;

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

        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;  //k从1开始捆绑
        while(k < s){
            cnt ++;
            v[cnt] = k * a;  //捆绑物品的体积
            w[cnt] = k * b;  //捆绑物品的价值
            s -= k;
            k <<= 1;
        }
        if(s){  //最后剩余的无法凑整的数
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }

    }

    for(int i = 1; i <= cnt; i ++){  //01背包一维优化求解
        for(int j = m; j >= v[i]; j --){
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[m] << endl;

}

int main(){

    solve();

    return 0;

}

4. 混合背包问题

4.1 模板题

混合背包问题

原题链接

描述

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

输出样例：

8

思想

  • 本质为多重背包问题
  • 将只能使用一次的视为一个物品的捆绑
  • 使用多次的用二进制优化捆绑
  • 使用无限次的按照背包的最大空间调整使用次数，再用二进制优化捆绑

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 3;

int dp[N];

int v[N], w[N];

void solve(){

    int n, m;
    cin >> n >> m;

    int cnt = 0;

    for(int i = 1; i <= n; i ++){
        int a, b, s;
        cin >> a >> b >> s;

        if(s == -1) s = 1;
        else if(s == 0) s = m / a;

        int k = 1;
        while(k < s){
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k <<= 1;
        }
        if(s){
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }

    }

    for(int i = 1; i <= cnt; i ++){
        for(int j = m; j >= v[i]; j --){
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[m] << endl;

}

int main(){

    solve();

    return 0;

}

5. 分组背包问题

5.1 模板题

分组背包问题

原题链接

描述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100

输入样例：

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

8

思想

  • 状态表示：
    • 集合：dp[j]表示背包体积不超过j时的价值
    • 属性：最大价值
  • 状态计算：
    • 分组：v[i][k]为i组的第k个物品的体积，w[i][k]为i组的第k个物品的价值
    • 对于每组进行最优决策：dp[j] = max(dp[j],dp[j - v[i][k]] + w[i][k])

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int dp[N];

int v[N][N], w[N][N];

void solve(){

    int n, m;
    cin >> n >>m;

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

        int s[i];
        cin >> s[i];

        for(int j = 1; j <= s[i]; j ++){
            cin >> v[i][j] >> w[i][j];
        }

        for(int j = m; j >= 0; j --){
            for(int k = 1; 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;

}

int main(){

    solve();

    return 0;

}

5.2 提高练习

1013. 机器分配

原题链接

描述

总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入格式
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；

接下来是一个N*M的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。

输出格式
第一行输出最大盈利值；

接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输出任意合法方案即可。

数据范围
1≤N≤10,
1≤M≤15
输入样例：

3 3
30 40 50
20 30 50
20 25 30

输出样例：

70
1 1
2 1
3 1

思想

  • 状态表示：
    • 集合：dp[i][j]表示前i个公司，使用服务器不超过j获得的盈利的集合
    • 属性：最大盈利
  • 状态计算：
    • 不选第i个公司的服务器：dp[i - 1][j]
    • 选择第i个公司的k个服务器：dp[i][j] = dp[i - 1][j - k] + w[i][k]
    • 集合属性为最大盈利，取两种方案max()：dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - k] + w[i][k])
  • 用num[i]记录第i个公司的服务器分配数量

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100;

int dp[N][N];

int w[N][N];

int num[N];

void solve(){

    int n, m;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> w[i][j];
        }
    }

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

    int j = m;

    for(int i = n; i ; i --){
        for(int k = 1; k <= j; k ++){
            if(dp[i][j] == dp[i - 1][j - k] + w[i][k]){
                num[i] = k;
                j -= k;
                break;
            }
        }
    }

    cout << dp[n][m] << endl;

    for(int i = 1; i <= n; i ++) cout << i << " " << num[i] << endl; 

}

int main(){

    solve();

    return 0;

}

6. 二维费用背包问题

6.1 模板题

二维费用的背包问题

原题链接

描述

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：

输出样例：

8

思想

  • 状态表示：
    • 集合：dp[i][j][k]表示前i个物品，体积不超过j，且重量不超过k的集合的价值
    • 属性：最大价值
  • 状态计算：
    • 不选第i个物品：dp[i][j][k] = dp[i - 1][j][k]
    • 选择第i个物品：dp[i][j][k] = dp[i - 1][j - v[i]][k - m[i]] + w[i]
    • 集合属性为最大价值，取两种方案max()：dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - v[i]][k - m[i]] + w[i])
  • 优化：dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + w[i])

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N][N];

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

void solve(){

    int n, V, M;

    cin >> n >> V >> M;

    for(int i = 1; i <= n; i ++) cin >> v[i] >> m[i] >> w[i];

    for(int i = 1; i <= n; i ++){
        for(int j = V; j >= v[i]; j --){
            for(int k = M; k >= m[i]; k --){
                dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + w[i]);
            }
        }
    }

    cout << dp[V][M] << endl;

}

int main(){

    solve();

    return 0;

}

6.2 提高练习

1020. 潜水员

原题链接

描述

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式
第一行有2个整数 m，n。它们表示氧，氮各自需要的量。

第二行为整数 k 表示气缸的个数。

此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。

输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

数据范围
1≤m≤21,
1≤n≤79,
1≤k≤1000,
1≤ai≤21,
1≤bi≤79,
1≤ci≤800
输入样例：

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

输出样例：

249

思想

  • 状态表示：
    • 集合：dp[i][j][k]表示前i个气瓶，氧气体积不少于j，氮气体积不少于k的重量
    • 属性：最小重量
  • 状态计算：
    • 不选第i个：dp[i][j][k] = dp[i - 1][j][k]
    • 选择第i个：dp[i][j][k] = dp[i - 1][j - v[i]][k - w[i]] + m[i]
    • 集合属性为最小重量，两种方案取min()：dp[i][j][k] = min(dp[i - 1][j][k],dp[i - 1][j - v[i]][k - w[i]] + m[i])
    • 初始化dp[0][0][0] = 0，其余dp[i][j][k] = 0x3f3f3f3f
  • 优化：dp[j][k] = min(dp[j][k],dp[j - v[i]][k - w[i]] + m[i])
  • 注意当j - v[i] < 0或者k - w[i] < 0时也满足集合的定义，当j - v[i] < 0或者k - w[i] < 0时，视为j - v[i] = 0或者k - w[i] = 0

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N][N];

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

void solve(){

    int V, W, n;

    cin >> V >> W >> n;

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;

    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> m[i];

    for(int i = 1; i <= n; i ++){
        for(int j = V; j >= 0; j --){
            for(int k = W; k >= 0; k --){
                dp[j][k] = min(dp[j][k],dp[max(0,j - v[i])][max(0,k - w[i])] + m[i]);
            }
        }
    }

    cout << dp[V][W] << endl;

}

int main(){

    solve();

    return 0;

}

1022. 宠物小精灵之收服

原题链接

描述

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而，野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。

如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围
0<N≤1000,
0<M≤500,
0<K≤100
输入样例1：

10 100 5
7 10
2 40
2 50
1 20
4 20

输出样例1：

3 30

思想

  • 状态表示：
    • 集合：d[i][j][k]表示前i个小精灵，消耗精灵球不超过j，且消耗皮卡丘体力不超过k的收集到的精灵数量
    • 属性：最大精灵数量
  • 状态计算：
    • 不选第i个小精灵：dp[i][j][k] = dp[i - 1][j][k]
    • 选择第i个小精灵：dp[i][j][k] = dp[i - 1][j -v[i]][k - m[i]] + 1
    • 集合属性为最大值，取两种方案max()：dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - v[i]][k - m[i]] + 1)
  • 优化：dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + 1)
  • 注意枚举k要从k = M - 1开始，因为皮卡丘体力不能为$0$
  • 遍历dp[j][k]，找到当dp[j][k] == dp[j][k - 1]时，消耗最少的体力k，用cnt记录

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int dp[N][N];

int v[N], m[N];

void solve(){

    int n, V, M;

    cin >> V >> M >> n;

    dp[0][0] = 0;

    for(int i = 1; i <= n; i ++) cin >> v[i] >> m[i];

    for(int i = 1; i <= n; i ++){
        for(int j = V; j >= v[i]; j --){
            for(int k = M - 1; k >= m[i]; k --){
                dp[j][k] = max(dp[j][k],dp[j - v[i]][k - m[i]] + 1);
            }
        }
    }

    int cnt = 0x3f3f3f3f;

    for(int i = 0; i <= V; i ++){
        for(int j = 0; j <= M - 1; j ++){
            if(dp[i][j] == dp[V][M - 1]) cnt = min(cnt,j);
        }
    }

    cout <<  dp[V][M - 1] << " " <<  M - cnt << endl;

}

int main(){

    solve();

    return 0;

}

7. 有依赖的背包问题

7.1 模板题

有依赖的背包问题

原题链接

描述

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数，表示最大价值。

数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围：

内部结点：1≤pi≤N;
根节点 pi=−1;

输出样例：

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出样例：

11

思想

  • 状态表示：
    • 集合：dp[i][j]表示第i个物品为根节点的字数，且选上i选法的体积不超过j的价值
    • 属性：最大价值
  • 状态计算：
    • 不选子树i：则其子节点的价值之和为0；
    • 选择子树i：递归处理所有子节点，选择最大的字节点的最大价值的子树

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int dp[N][N];

int e[N], ne[N], h[N], idx;

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

int n, m;

int v[N], w[N];

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;

}

void solve(){

    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;
        if(p){
            add(p, i);
        }
    }

    dfs(root);

    cout << dp[root][m] << endl;

}

int main(){

    solve();

    return 0;

}

7.2 提高练习

487. 金明的预算方案

原题链接

描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。

今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的

如果要买归类为附件的物品，必须先买该附件所属的主件。

每个主件可以有0个、1个或2个附件。

附件不再有从属于自己的附件。

金明想买的东西很多，肯定会超过妈妈限定的N元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

他还从因特网上查到了每件物品的价格（都是10元的整数倍）。

他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，…，jk，则所求的总和为：

v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式
输入文件的第1行，为两个正整数，用一个空格隔开：N m，其中N表示总钱数，m为希望购买物品的个数。

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q，其中v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件。

如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号。

输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

数据范围
N<32000,m<60,v<10000

输出样例：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出样例：

2200

思想

  • 状态表示：
    • 集合：dp[i][j]表示前i个物品，总体积不超过j的价值
    • 属性：最大价值
  • 状态计算：
    • 不选第i个物品：dp[i][j] = dp[i - 1][j]
    • 选择第i个物品：dp[i][j] = dp[i - 1][j - v[i]] + w[i]
  • 由于每个子物品没有再附属的子物品，所以我们可以考虑枚举选择子物品的方案
  • 我们可以对于每一个集合，不选的话无需更新，如果购买必须购买主件，所以我们可以先购买主件，然后枚举附件的选择方案

代码

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef pair<int, int> PII;

const int N = 70, M = 32010;

int n, m;
PII ma[N];
vector<PII> sv[N];
int dp[M];

void solve(){

    cin >> m >> n;

    for (int i = 1; i <= n; i ++ ) {
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) ma[i] = {v, v * w};
        else sv[q].push_back({v, v * w});
    }

    for (int i = 1; i <= n; i ++ ) 
        if (ma[i].fi) {
            for (int j = m; j >= 0; j -- ) {
                for (int k = 0; k < 1 << sv[i].size(); k ++ ) {
                    int v = ma[i].fi, w = ma[i].se;
                    for (int u = 0; u < sv[i].size(); u ++ ) 
                        if (k >> u & 1) {
                            v += sv[i][u].fi;
                            w += sv[i][u].se;
                        }
                    if (j >= v) dp[j] = max(dp[j], dp[j - v] + w);
                }
            }
        }

    cout << dp[m] << endl;

}

int main(){

    solve();

    return 0;
}

8. 背包问题求方案数

8.1 模板题

背包问题求方案数

原题链接

描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示 方案数 模 109+7 的结果。

数据范围
0<N,V≤1000
0<vi,wi≤1000

输出样例：

4 5
1 2
2 4
3 4
4 6

输出样例：

2

思想

  • 状态表示：
    • 集合：cnt[j]表示背包容积为j时最佳的方案
    • 属性：方案的数量
  • 状态计算：
    • 若新的物品方案比原方案总价值增大：cnt[j] = cnt[j - v[i]]
    • 若新的物品方案与原方案总价值相同：cnt[j] = cnt[j] + cnt[j - v[i]]
    • 初始化cnt[j] = 1

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

const int mod = 1e9 + 7;

int dp[N];

int cnt[N];

int v[N], w[N];

void solve(){

    int n, m;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    for(int i = 0; i <= m; i ++) cnt[i] = 1;

    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= v[i]; j --){
            int t = dp[j - v[i]] + w[i];
            if(t > dp[j]){
                dp[j] = t;
                cnt[j] = cnt[j - v[i]];
            }
            else if(t == dp[j]){
                cnt [j] = (cnt[j] + cnt[j - v[i]]) % mod;
            }
        }
    }

    cout << cnt[m] << endl;

}

int main(){

    solve();

    return 0;

}

9. 背包问题求具体方案

9.1 模板题

背包问题求具体方案

原题链接

描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

数据范围
0<N,V≤1000
0<vi,wi≤1000

输出样例：

4 5
1 2
2 4
3 4
4 6

输出样例：

1 4

思想

  • 由于要字典序输出方案，故需要逆序01背包进行更新
  • 逆序判断是否选取物品即为字典序

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int dp[N][N];

int v[N], w[N];

void solve(){

    int n, m;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    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 j = m;
    for(int i = 1; i <= n; i ++){

        if(j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]){
            cout << i << ' ';
            j -= v[i];
        }

    }

}

int main(){

    solve();

    return 0;

}
DP背包问题
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
823. 排列 (递归搜索树 · 排列)

							
							

							
AtCoder Beginner Contest 273（A~D）

							
							

							
河工院首届工业设计大赛程序组（挑战赛）题解

							
							

							
4219. 找倍数

							
							

							
AcWing 第69场周赛

							
							

							
727. 菱形 (曼哈顿距离)