多重背包、分组背包、混合背包和多维背包

一、多重背包

1、介绍

物品个数是多个，但不是无穷个。

例题：多重背包

登录—专业IT笔试面试备考平台_牛客网

2、分析

dp[i][j]表示在[1, i]中选，重量不超过j的最大价值
不选i：dp[i][j] = dp[i - 1][j];
选i：由于物品个数不是无限的，所以不能优化只能一个一个写
选一个：dp[i][j] = dp[i - 1][j - w[i]] + v[i];
选二个：dp[i][j] = dp[i - 1][j - 2 * w[i]] + 2 * v[i];
..... 
选最多x[i]个：dp[i][j] = dp[i - 1][j - x[i] * w[i]] + x[i] * v[i];
当然枚举过程中j - k * w[i] >= 0
初始化返回值都和之前问题一样

3、代码

#include <bits/stdc++.h>
using namespace std;
int w[110];
int v[110];
int x[110];
int n, t;int dp[110][110];
int main()
{cin >> n >> t;for(int i = 1; i <= n; i++)cin >> x[i] >> w[i] >> v[i]; for(int i = 1; i <= n; i++){for(int j = 0; j <= t; j++){for(int k = 0; k <= x[i] && j - k * w[i] >= 0; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);}}cout << dp[n][t];return 0;
}

4、空间优化

只用到了左上方的数据，所以从右向左

#include <bits/stdc++.h>
using namespace std;
int w[110];
int v[110];
int x[110];
int n, t;int dp[110];
int main()
{cin >> n >> t;for(int i = 1; i <= n; i++)cin >> x[i] >> w[i] >> v[i]; for(int i = 1; i <= n; i++){for(int j = t; j >= 0; j--){for(int k = 0; k <= x[i] && j - k * w[i] >= 0; k++)dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);}}cout << dp[t];return 0;
}

5、二进制优化

二进制优化：优化后最终结果会把多重背包变成01背包
其实多重背包不做任何优化也能看作01背包，因为个数有限，可以把每一个物品拆出来
基于这种思想不难想到可以把同一种物品的10进制个数通过二进制表示出来，这样优化的是logX
假设一个物品个数是9，重量w，价值v
9 = 1 + 2 + 4 + 2，即可以看成有4种物品分别的重量和价值是[w, v], [2w, 2v], [4w, 4v], [2w, 2v]
然后进行01背包处理
这样从O(n * t * x)->O(n * t * logx)
没有数量数组，原数组由于优化，每种物品分成了logX种物品，所以大小还要乘logX

求方案数不能二进制优化，因为同一种物品被我们分成了logx种物品
即优化后的不同数据不能代表不同的物品，也就不能代表一种方案

int w[5 * 110];
int v[5 * 110];
int n, t;
int sz; // 新的个数用sz记录
int dp[110];
int main()
{cin >> n >> t;for(int i = 1; i <= n; i++){int x, y, z;cin >> x >> y >> z;// 同一物品开始二进制分类int p = 1;while(x >= p){sz++;x -= p;w[sz] = y * p;v[sz] = z * p;p *= 2;}if(x){sz++;w[sz] = y * x;v[sz] = z * x;}}for(int i = 1; i <= sz; i++){for(int j = t; j >= w[i]; j--){dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}}cout << dp[t];return 0;
}

二、分组背包

1、介绍

在每一组中挑一个物品

例题：分组背包

P1757 通天之分组背包 - 洛谷

2、分析

dp[i][j]表示在小组[1, i]中选，每组选一个物品，重量不超过j的最大价值
不选i: dp[i][j] = dp[i - 1][j];
选i: 选i组的第一个: dp[i][j] = dp[i - 1][j - w[i][0]] + v[i][0];
选i: 选i组的第二个: dp[i][j] = dp[i - 1][j - w[i][1]] + v[i][1];
.....
选i: 选i组的第x个: dp[i][j] = dp[i - 1][j - w[i][x - 1]] + v[i][x - 1];

3、代码

// https://www.luogu.com.cn/problem/P1757
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
int n, m;
vector<pii> g[110];
int k = 0;int dp[110][1010];
int main()
{cin >> m >> n;for(int i = 1; i <= n; i++){int W, V, K;cin >> W >> V >> K;g[K].push_back({W, V});k = max(k, K);}for(int i = 1; i <= k; i++){for(int j = m; j >= 0; j--){dp[i][j] = dp[i - 1][j];for(auto& [a, b] : g[i]){if(j - a >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - a] + b);}}}cout << dp[k][m];return 0;
}

4、空间优化

空间优化：用的是左上，所以从右向左

int dp[1010];
int main()
{cin >> m >> n;for(int i = 1; i <= n; i++){int W, V, K;cin >> W >> V >> K;g[K].push_back({W, V});k = max(k, K);}for(int i = 1; i <= k; i++){for(int j = m; j >= 0; j--){for(auto& [a, b] : g[i]){if(j - a >= 0)dp[j] = max(dp[j], dp[j - a] + b);}}}cout << dp[m];return 0;
}

三、混合背包

1、介绍

01背包，完全背包，多重背包，分组背包结合在一起的背包问题

例题：樱花

P1833 樱花 - 洛谷

2、分析

就是遇到一种物品属于什么背包问题就用对应的状态方程解决即可。

3、代码

int m, n;
int t[10010];
int c[10010];
int p[10010];int dp[10010][1010];
int main()
{int h1, m1, h2, m2;char ch;cin >> h1 >> ch >> m1 >> h2 >> ch >> m2 >> n;m = h2 * 60 + m2 - h1 * 60 - m1;for(int i = 1; i <= n; i++)cin >> t[i] >> c[i] >> p[i];for(int i = 1; i <= n; i++){if(p[i] == 0){for(int j = 0; j <= m; j++){dp[i][j] = dp[i - 1][j];if(j - t[i] >= 0)dp[i][j] = max(dp[i][j], dp[i][j - t[i]] + c[i]);}}else {for(int j = m; j >= 0; j--){dp[i][j] = dp[i - 1][j];for(int k = 1; k <= p[i] && j - k * t[i] >= 0; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - k * t[i]] + k * c[i]);}}}cout << dp[n][m];return 0;
}

4、空间优化

注意完全背包是从左向右即可

int dp[1010];
int main()
{int h1, m1, h2, m2;char ch;cin >> h1 >> ch >> m1 >> h2 >> ch >> m2 >> n;m = h2 * 60 + m2 - h1 * 60 - m1;for(int i = 1; i <= n; i++)cin >> t[i] >> c[i] >> p[i];for(int i = 1; i <= n; i++){if(p[i] == 0){for(int j = t[i]; j <= m; j++){dp[j] = max(dp[j], dp[j - t[i]] + c[i]);}}else {for(int j = m; j >= t[i]; j--){for(int k = 1; k <= p[i] && j - k * t[i] >= 0; k++)dp[j] = max(dp[j], dp[j - k * t[i]] + k * c[i]);}}}cout << dp[m];return 0;
}

四、多维背包

1、介绍

限制条件增多的背包问题，必须要空间优化。

例题：L 国的战斗之间谍

P1910 L 国的战斗之间谍 - 洛谷

2、分析

dp[i][j][k]表示在[1, i]中选，暴露不超过j，工资不超过j的最大价值
不选i: dp[i][j][j] = dp[i - 1][j][k];
  选i: dp[i][j][k] = dp[i - 1][j - b[i]][k - c[i]] + a[i];

3、空间优化代码

从右向左

// https://www.luogu.com.cn/problem/P1910
// 多维背包：限制条件变多，那就加维数
#include <bits/stdc++.h>
using namespace std;
int n, m, x;
int a[110];
int b[110];
int c[110];
int dp[1010][1010];// dp[i][j][k]表示在[1, i]中选，暴露不超过j，工资不超过j的最大价值
// 不选i: dp[i][j][j] = dp[i - 1][j][k];
//   选i: dp[i][j][k] = dp[i - 1][j - b[i]][k - c[i]] + a[i];
// 必须空间优化
int main()
{cin >> n >> m >> x;for(int i = 1; i <= n; i++)cin >> a[i] >> b[i] >> c[i];for(int i = 1; i <= n; i++){for(int j = m; j >= b[i]; j--){for(int k = x; k >= c[i]; k--){dp[j][k] = max(dp[j][k], dp[j - b[i]][k - c[i]] + a[i]);}}}cout << dp[m][x];return 0;
}

五、例题

1、摆花

P1077 [NOIP 2012 普及组] 摆花 - 洛谷

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[110];
const int mod = 1e6 + 7;// dp[i][j]表示在[1, i]种物品种选，个数刚好j的总方案数
// 不选i:   dp[i][j] = dp[i - 1][j];
// 选一个i: dp[i][j] += dp[i - 1][j - 1];
// 选二个i: dp[i][j] += dp[i - 1][j - 2];
// ....
// 选a[i]个i: dp[i][j] += dp[i - 1][j - a[i]];
// j - x >= 0;
// 初始化：dp[0][0] = 1; dp[0][j] = 0int main()
{cin >> n >> m;vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));dp[0][0] = 1;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){for(int k = 0; k <= a[i] && j - k >= 0; k++)dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;}}cout << dp[n][m];return 0;
}

2、排兵布阵

P5322 [BJOI2019] 排兵布阵 - 洛谷

#include <bits/stdc++.h>
using namespace std;
int s, n, m;
int g[110][110];
int dp[110][20010];// https://www.luogu.com.cn/problem/P5322
// 对于每一个人的每一个城堡我们都能*2+1找到最少占领这个城堡的分配士兵数
// 即问题转化成了在每一组城堡中我挑出一个数，计算能占领几个这样的城堡
// dp[i][j]表示在[1, i]的城堡中，派出不超过m名士兵后的最大得分
// 存储数组g[110][110]，一维城堡编号，二维玩家编号，每一行排好序
// 不派：dp[i][j] = dp[i - 1][j];
// 派g[i][p]的士兵争夺城堡i: dp[i][j] = dp[i - 1][j - g[i][p]] + i * p;
int main()
{cin >> s >> n >> m;for(int i = 1; i <= s; i++){for(int j = 1; j <= n; j++){cin >> g[j][i];g[j][i] = 2 * g[j][i] + 1;}}for(int i = 1; i <= n; i++)sort(g[i] + 1, g[i] + s + 1);for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] = dp[i - 1][j];for(int p = 1; p <= s; p++){if(j - g[i][p] >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - g[i][p]] + p * i);}}}cout << dp[n][m];return 0;
}