多重背包、混合背包
P1776 宝物筛选
一共有n种货物, 背包容量为 t
每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
请返回选择货物不超过背包容量的情况下，能得到的最大的价值
多重背包不进行枚举优化
- 严格位置依赖的动态规划
#include <iostream>
#include <vector>using namespace std;// 时间复杂度 O(n * w * 每种商品的平均个数)
int main() {int n, w;cin >> n >> w;vector<int> cost(n + 1);vector<int> value(n + 1);vector<int> cnt(n + 1);for (int i = 1; i <= n; ++i)cin >> value[i] >> cost[i] >> cnt[i];// dp[i][j] 表示前 i 号物品，在每种物品不超过限制，且总重量也不超过 j 的情况下，获得的最大价值vector<vector<int>> dp(n + 1, vector<int>(w + 1));// 表示没有货物的情况下，背包容量不管是多少，最大价值都是 0fill(dp[0].begin(), dp[0].end(), 0);for (int i = 1; i <= n; ++i) {for (int j = 0; j <= w; ++j) {// 一个都不选dp[i][j] = dp[i - 1][j];// 选若干个，不超过每种物品的限制for (int k = 1; k <= cnt[i] && j - k * cost[i] >= 0; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - k * cost[i]] + k * value[i]);}}cout << dp[n][w];
}
- 空间压缩
#include <iostream>
#include <vector>using namespace std;// 时间复杂度 O(n * w * 每种商品的平均个数)
int main() {int n, w;cin >> n >> w;vector<int> cost(n + 1);vector<int> value(n + 1);vector<int> cnt(n + 1);for (int i = 1; i <= n; ++i)cin >> value[i] >> cost[i] >> cnt[i];// dp[i][j] 表示前 i 号物品，在每种物品不超过限制，且总重量也不超过 j 的情况下，获得的最大价值// 首行全 0vector<int> dp(w + 1, 0);for (int i = 1; i <= n; ++i) {for (int j = w; j >= 0; j--) {// 一个都不选，或者选若干个，但不超过每种物品的限制for (int k = 1; k <= cnt[i] && j - k * cost[i] >= 0; k++)dp[j] = max(dp[j], dp[j - k * cost[i]] + k * value[i]);}}cout << dp[w];
}
多重背包通过二进制分组转化成 01 背包(模版)
#include <iostream>
#include <vector>using namespace std;// 时间复杂度 O(t * (log(第 1 种商品的个数) + log(第 2 种商品的个数) + ... + log(第 n 种商品的个数)))
int main() {// w 为背包容量int n, w;cin >> n >> w;// 衍生出的物品总数int m = 0;vector<int> value(1);vector<int> cost(1);for (int i = 1, _value, _cost, _cnt; i <= n; ++i) {cin >> _value >> _cost >> _cnt;// 二进制分组：每组放 2^(k-1) 个当前物品，时间复杂度为 O(log(_cnt))for (int k = 1; k <= _cnt; k <<= 1) {value.emplace_back(k * _value);cost.emplace_back(k * _cost);_cnt -= k;m++;}// 最后剩下的归为一组if (_cnt > 0) {value.emplace_back(_cnt * _value);cost.emplace_back(_cnt * _cost);m++;}}// 01 背包空间压缩vector<int> dp(w + 1, 0);for (int i = 1; i <= m; ++i)for (int j = w; j >= cost[i]; j--)dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);cout << dp[w];
}
多重背包单调队列优化
- 严格位置依赖的动态规划
#include <iostream>
#include <vector>
#include <queue>using namespace std;// 当前来到 i 号货物，需要 j 位置的指标，返回指标值
int getValue(vector<vector<int>> &dp, vector<int> &cost, vector<int> &value, int i, int j) {return dp[i - 1][j] - (j / cost[i]) * value[i];
}// 时间复杂度 O(n * w)
int main() {int n, w;cin >> n >> w;vector<int> cost(n + 1);vector<int> value(n + 1);vector<int> cnt(n + 1);for (int i = 1; i <= n; ++i)cin >> value[i] >> cost[i] >> cnt[i];// dp[i][j] 表示前 i 号物品，在每种物品不超过限制，且总重量也不超过 j 的情况下，获得的最大价值vector<vector<int>> dp(n + 1, vector<int>(w + 1));// 表示没有货物的情况下，背包容量不管是多少，最大价值都是 0fill(dp[0].begin(), dp[0].end(), 0);// 单调队列，存放列号deque<int> q;for (int i = 1; i <= n; ++i) {// 同余分组for (int mod = 0; mod <= min(w, cost[i] - 1); mod++) {q.clear();for (int j = mod; j <= w; j += cost[i]) {// 弹出收益不如当前位置的列号while (!q.empty() && getValue(dp, cost, value, i, q.back()) <= getValue(dp, cost, value, i, j))q.pop_back();q.emplace_back(j);// 单调队列头部过期if (q.front() == j - cost[i] * (cnt[i] + 1))q.pop_front();dp[i][j] = getValue(dp, cost, value, i, q.front()) + (j / cost[i]) * value[i];}}}cout << dp[n][w];
}
- 空间压缩
#include <iostream>
#include <vector>
#include <queue>using namespace std;// 当前来到 i 号货物，需要 j 位置的指标，返回指标值
int getValue(vector<int> &dp, vector<int> &cost, vector<int> &value, int i, int j) {return dp[j] - (j / cost[i]) * value[i];
}// 时间复杂度 O(n * w)
int main() {int n, w;cin >> n >> w;vector<int> cost(n + 1);vector<int> value(n + 1);vector<int> cnt(n + 1);for (int i = 1; i <= n; ++i)cin >> value[i] >> cost[i] >> cnt[i];// dp[i][j] 表示前 i 号物品，在每种物品不超过限制，且总重量也不超过 j 的情况下，获得的最大价值// 首行全 0vector<int> dp(w + 1, 0);// 单调队列，存放列号deque<int> q;for (int i = 1; i <= n; ++i) {for (int mod = 0; mod <= min(w, cost[i] - 1); mod++) {q.clear();// 先把 cnt[i] 个的指标进入单调队列for (int j = w - mod, count = 1; j >= 0 && count <= cnt[i]; j -= cost[i], count++) {while (!q.empty() && getValue(dp, cost, value, i, q.back()) <= getValue(dp, cost, value, i, j))q.pop_back();q.emplace_back(j);}for (int j = w - mod, enter = j - cost[i] * cnt[i]; j >= 0; j -= cost[i], enter -= cost[i]) {// 窗口进入 enter 位置的指标if (enter >= 0) {while (!q.empty()&& getValue(dp, cost, value, i, q.back()) <= getValue(dp, cost, value, i, enter))q.pop_back();q.emplace_back(enter);}dp[j] = getValue(dp, cost, value, i, q.front()) + (j / cost[i]) * value[i];if (q.front() == j) q.pop_front();}}}cout << dp[w];
}
P1833 樱花
#include <iostream>
#include <vector>using namespace std;int main() {string time1, time2;cin >> time1 >> time2;int h1 = stoi(time1.substr(0, time1.find(':')));int m1 = stoi(time1.substr(time1.find(':') + 1, time1.size()));int h2 = stoi(time2.substr(0, time2.find(':')));int m2 = stoi(time2.substr(time2.find(':') + 1, time2.size()));// w 为背包容量int w = (h2 - h1) * 60 + (m2 - m1);// 物品种类数int n;cin >> n;// 衍生出的物品总数int m = 0;vector<int> value(1);vector<int> cost(1);for (int i = 1, _value, _cost, _cnt; i <= n; ++i) {cin >> _cost >> _value >> _cnt;// 可以看无数遍，但实际有时间限制，w 时间内，即使每种树只要一分钟，那最多也就看 w 遍if (_cnt == 0) _cnt = w;// 二进制分组：每组放 2^(k-1) 个当前物品，时间复杂度为 O(log(_cnt))for (int k = 1; k <= _cnt; k <<= 1) {value.emplace_back(k * _value);cost.emplace_back(k * _cost);_cnt -= k;m++;}// 最后剩下的归为一组if (_cnt > 0) {value.emplace_back(_cnt * _value);cost.emplace_back(_cnt * _cost);m++;}}// 01 背包空间压缩vector<int> dp(w + 1, 0);for (int i = 1; i <= m; ++i)for (int j = w; j >= cost[i]; j--)dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);cout << dp[w];
}
混合背包 + 多重背包普通窗口优化
混合背包 + 多重背包普通窗口优化
能成功找零的钱数种类
每一种货币都给定面值val[i]，和拥有的数量cnt[i]
想知道目前拥有的货币，在钱数为1、2、3...m时
能找零成功的钱数有多少
也就是说当钱数的范围是1~m
返回这个范围上有多少可以找零成功的钱数
#include <iostream>using namespace std;const int MAX_N = 101;
const int MAX_M = 100001;
// n 为硬币总数，m 为背包容量
int n, m;
// 硬币面额
int value[MAX_N];
// 硬币个数
int cnt[MAX_N];
// dp[i][j] 表示前 i 种硬币，在数量不超过限制的情况下，能否刚好凑出 j
bool dp[MAX_M];int compute() {for (int i = 1; i <= m; ++i) dp[i] = false;dp[0] = true;for (int i = 1; i <= n; ++i) {if (cnt[i] == 1) {// 当前硬币只有一个// 01 背包的空间压缩实现是从右往左更新for (int j = m; j >= value[i]; j--)if (dp[j - value[i]])dp[j] = true;} else if (value[i] * cnt[i] > m) {// 这种硬币的总值超过背包容量// 完全背包的空间压缩实现是从左往右更新for (int j = value[i]; j <= m; ++j)if (dp[j - value[i]])dp[j] = true;} else {// 多重背包的空间压缩实现// 每一组都是从右往左更新// 同余分组for (int mod = 0; mod < value[i]; mod++) {int trueCnt = 0;for (int j = m - mod, size = 0; j >= 0 && size <= cnt[i]; j -= value[i], size++)trueCnt += dp[j] ? 1 : 0;for (int j = m - mod, l = j - value[i] * (cnt[i] + 1); j >= 1; j -= value[i], l -= value[i]) {if (dp[j]) {trueCnt--;} else {if (trueCnt != 0) dp[j] = true;}if (l >= 0) trueCnt += dp[l] ? 1 : 0;}}}}int res = 0;for (int i = 1; i <= m; i++)if (dp[i]) res++;return res;
}int main() {cin >> n >> m;while (n != 0 || m != 0) {for (int i = 1; i <= n; ++i) cin >> value[i];for (int i = 1; i <= n; ++i) cin >> cnt[i];cout << compute() << endl;cin >> n >> m;}
}
