01背包、有依赖的背包
P1048 [NOIP2005 普及组] 采药
01背包(模版)
给定一个正数 t，表示背包的容量
有 m 个货物，每个货物可以选择一次
每个货物有自己的体积 costs[i] 和价值 values[i]
返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
返回最大的价值
- 二维 dp 数组
#include <iostream>
#include <vector>
using namespace std;
int bag(vector<int> &cost, vector<int> &value, int t, int n) {
// dp[i][j] 表示在前 i 种物品中选择，总代价不超过 j 的情况下，能获得的最大价值
vector<vector<int>> dp(n + 1, vector<int>(t + 1));
// 第一行为 0
fill(dp[0].begin(), dp[0].end(), 0);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= t; ++j) {
// 不选 i 号物品，则最大价值和在前 i - 1 个物品中选，总代价不超过 j 的情况下能获得的最大价值一样
dp[i][j] = dp[i - 1][j];
// 选 i 号物品，价值就是 i 号物品的价值加上在前 i - 1 个物品中选，总代价不超过 j - cost[i] 的情况下能获得的最大价值
if (j - cost[i] >= 0)
dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + value[i]);
}
}
// 返回在 n 种物品中选择，总代价不超过 t 的情况下，能获得的最大价值
return dp[n][t];
}
int main() {
// t 为背包容量，n 为物品种数
int t, n;
cin >> t >> n;
// 物品从 1 编号
vector<int> cost(n + 1);
vector<int> value(n + 1);
for (int i = 1; i <= n; ++i)
cin >> cost[i] >> value[i];
cout << bag(cost, value, t, n);
}
- 空间压缩
#include <iostream>
#include <vector>
using namespace std;
int bag(vector<int> &cost, vector<int> &value, int t, int n) {
// 原矩阵的每一行，逐行往下，第一行为 0
vector<int> dp(t + 1, 0);
for (int i = 1; i <= n; ++i)
// 如果从左往右的话就需要两个一维数组了，因为从左往右的过程中会覆盖掉 dp[j - cost[i]]
// 从右往左可以避免这个问题
// dp[j] 继承自上一行的 dp[j] 不变，表示不选 i 号物品
// 或者选 i 号物品，价值就是 i 号物品的价值加上在前 i - 1 个物品中选，总代价不超过 j - cost[i] 的情况下能获得的最大价值
// dp[j - cost[i]] 也来自上一行
for (int j = t; j - cost[i] >= 0; j--)
dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
// 返回在 n 种物品中选择，总代价不超过 t 的情况下，能获得的最大价值
return dp[t];
}
int main() {
// t 为背包容量，n 为物品种数
int t, n;
cin >> t >> n;
// 物品从 1 编号
vector<int> cost(n + 1);
vector<int> value(n + 1);
for (int i = 1; i <= n; ++i)
cin >> cost[i] >> value[i];
cout << bag(cost, value, t, n);
}
bytedance-006. 夏季特惠
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
// 返回在 n 种物品中选择，总代价不超过 x 的情况下，能获得的最大价值
ll bag(vector<int> &cost, vector<ll> &value, int x) {
int n = cost.size() - 1;
vector<ll> dp(x + 1, 0);
for (int i = 1; i <= n; ++i)
for (int j = x; j - cost[i] >= 0; j--)
dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
return dp[x];
}
int main() {
// x 为预算
int n, x;
cin >> n >> x;
// 待考虑的商品，下标从 1 开始
vector<int> cost(1);
// 快乐值
vector<ll> value(1);
// 获得的快乐值
ll res = 0;
int before, now;
ll happy;
for (int i = 1; i <= n; ++i) {
cin >> before >> now >> happy;
int val = before - now - now;
if (val > 0) {
// 优惠的钱比购买价格还高，一定购买，会使心里预算增加
x += val;
res += happy;
} else {
cost.emplace_back(-val);
value.emplace_back(happy);
}
}
cout << res + bag(cost, value, x);
}
494. 目标和
- 暴力递归
#include <vector>
using namespace std;
class Solution {
public:
int res;
// 暴力递归
void recursive(vector<int> &nums, int target, int curIndex, int sum) {
if (curIndex == nums.size()) {
if (sum == target) res++;
return;
}
recursive(nums, target, curIndex + 1, sum + nums[curIndex]);
recursive(nums, target, curIndex + 1, sum - nums[curIndex]);
}
int findTargetSumWays(vector<int> &nums, int target) {
res = 0;
recursive(nums, target, 0, 0);
return res;
}
};
- 带返回值的暴力递归
#include <vector>
using namespace std;
class Solution {
public:
int recursive(vector<int> &nums, int target, int curIndex, int sum) {
if (curIndex == nums.size())
return sum == target ? 1 : 0;
return recursive(nums, target, curIndex + 1, sum + nums[curIndex])
+ recursive(nums, target, curIndex + 1, sum - nums[curIndex]);
}
int findTargetSumWays(vector<int> &nums, int target) {
return recursive(nums, target, 0, 0);
}
};
- 记忆化搜索
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
unordered_map<int, unordered_map<int, int>> dp;
// 记忆化搜索版
// 本来使用 dp[curIndex][sum] 记录，但是 sum 可能是负数
// 所以用二级哈希表模拟
int recursive(vector<int> &nums, int target, int curIndex, int sum) {
if (curIndex == nums.size())
return sum == target ? 1 : 0;
if (dp.find(curIndex) != dp.end() && dp[curIndex].find(sum) != dp[curIndex].end())
return dp[curIndex][sum];
int res = recursive(nums, target, curIndex + 1, sum + nums[curIndex])
+ recursive(nums, target, curIndex + 1, sum - nums[curIndex]);
dp[curIndex].emplace(sum, res);
return res;
}
int findTargetSumWays(vector<int> &nums, int target) {
return recursive(nums, target, 0, 0);
}
};
- 严格位置依赖的动态规划
#include <vector>
using namespace std;
class Solution {
public:
// todo
int findTargetSumWays(vector<int> &nums, int target) {
int s = 0;
for (const auto &item: nums)
s += item;
// 不在范围内，凑不出来
if (target < -s || target > s) return 0;
int n = nums.size();
int m = 2 * s + 1;
// 原本的 dp[i][j] 含义:
// nums[0, i-1] 范围上，已经形成的累加和是 sum
// 为了避免 sum 为负数的情况，dp[i][j] 平移为 dp[i][j + s]
vector<vector<int>> dp(n + 1, vector<int>(m));
dp[n][target + s] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = -s; j <= s; j++) {
if (j + nums[i] + s < m)
dp[i][j + s] = dp[i + 1][j + nums[i] + s];
if (j - nums[i] + s >= 0)
dp[i][j + s] += dp[i + 1][j - nums[i] + s];
}
}
return dp[0][s];
}
};
- 01 背包
#include <vector>
using namespace std;
class Solution {
public:
// 求非负数组 nums 有多少个子序列累加和是 t
// 01 背包问题(子集累加和严格是 t) + 空间压缩
// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
int subsets(vector<int> &nums, int t) {
if (t < 0) return 0;
vector<int> dp(t + 1, 0);
dp[0] = 1;
for (int num: nums)
for (int j = t; j - num >= 0; j--)
dp[j] += dp[j - num];
return dp[t];
}
// 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3
// 其中一个方案是 : +1 -2 +3 -4 +5 = 3
// 该方案中取了正的集合为A = {1，3，5}
// 该方案中取了负的集合为B = {2，4}
// 所以任何一种方案，都一定有 sum(A) - sum(B) = target
// 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：
// sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)
// 2 * sum(A) = target + 数组所有数的累加和
// sum(A) = (target + 数组所有数的累加和) / 2
// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
// 那么就一定对应一种target的方式
// 比如非负数组nums，target = 1, nums所有数累加和是11
// 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6
// 因为，子集累加和6 - 另一半的子集累加和5 = 1（target)
// 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量
// 至此已经转化为01背包问题了
int findTargetSumWays(vector<int> &nums, int target) {
int sum = 0;
for (int num: nums) sum += num;
// 范围外凑不出 target，奇偶性不一致也凑不出
if (target < -sum || sum < target || ((target & 1) ^ (sum & 1)) == 1) return 0;
return subsets(nums, (target + sum) >> 1);
}
};
1049. 最后一块石头的重量 II
#include <vector>
using namespace std;
class Solution {
public:
// 非负数组 nums 中，子序列累加和不超过 t，但是最接近 t 的累加和是多少
// 01 背包问题(子集累加和尽量接近 t) + 空间压缩
int getNear(vector<int> &nums, int t) {
vector<int> dp(t + 1);
for (int num: nums)
for (int j = t; j - num >= 0; j--)
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
dp[j] = max(dp[j], dp[j - num] + num);
return dp[t];
}
int lastStoneWeightII(vector<int> &stones) {
int sum = 0;
for (int num: stones)
sum += num;
// nums 中随意选择数字，累加和一定要 <= sum / 2，又尽量接近
int near = getNear(stones, sum / 2);
return sum - near - near;
}
};
P1064 [NOIP2006 提高组] 金明的预算方案
有依赖的背包(模版)
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 代价
vector<int> cost(m + 1);
// 收益
vector<int> value(m + 1);
// 是否是主商品
vector<bool> king(m + 1);
// 主商品的附属商品
vector<vector<int>> follows(m + 1);
// 编号从 1 开始
for (int i = 1, v, p, q; i <= m; ++i) {
cin >> v >> p >> q;
cost[i] = v;
value[i] = v * p;
king[i] = q == 0;
if (q != 0) follows[q].emplace_back(i);
}
// dp[i][j] 表示前 i 个商品中，只关心主商品，并且进行展开，花费不超过 j 的情况下，获得的最大收益
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 上次展开的主商品编号
int pre = 0;
for (int i = 1, fan1, fan2; i <= m; ++i) {
// 跳过附属商品
if (!king[i]) continue;
for (int j = 0; j <= n; ++j) {
// 可能性1: 不考虑当前主商品
dp[i][j] = dp[pre][j];
// 可能性2: 考虑当前主商品，只要主
if (j - cost[i] >= 0)
dp[i][j] = max(dp[i][j],
dp[pre][j - cost[i]] + value[i]);
// fan1: 如果有附 1 商品，编号给 fan1，如果没有，fan1 == -1
// fan2: 如果有附 2 商品，编号给 fan2，如果没有，fan2 == -1
fan1 = follows[i].size() >= 1 ? follows[i][0] : -1;
fan2 = follows[i].size() >= 2 ? follows[i][1] : -1;
// 可能性3: 主 + 附1
if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0)
dp[i][j] = max(dp[i][j],
dp[pre][j - cost[i] - cost[fan1]] + value[i] + value[fan1]);
// 可能性4: 主 + 附2
if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0)
dp[i][j] = max(dp[i][j],
dp[pre][j - cost[i] - cost[fan2]] + value[i] + value[fan2]);
// 可能性5: 主 + 附1 + 附2
if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0)
dp[i][j] = max(dp[i][j],
dp[pre][j - cost[i] - cost[fan1] - cost[fan2]] + value[i] + value[fan1] + value[fan2]);
}
pre = i;
}
cout << dp[pre][n];
}
- 空间压缩
#include <vector>
#include <iostream>
using namespace std;
int main() {
// m 种商品，总金额 n
int n, m;
cin >> n >> m;
// 代价
vector<int> cost(m + 1);
// 收益
vector<int> value(m + 1);
// 是否是主商品
vector<bool> king(m + 1);
// 主商品的附属商品
vector<vector<int>> follows(m + 1);
// 编号从 1 开始
for (int i = 1, v, p, q; i <= m; ++i) {
cin >> v >> p >> q;
cost[i] = v;
value[i] = v * p;
king[i] = q == 0;
if (q != 0) follows[q].emplace_back(i);
}
// dp[i][j] 表示前 i 个商品中，只关心主商品，并且进行展开，花费不超过 j 的情况下，获得的最大收益
// 首行为 0
vector<int> dp(n + 1, 0);
for (int i = 1, fan1, fan2; i <= m; ++i) {
// 跳过附属商品
if (!king[i]) continue;
// 从右往左
for (int j = n; j - cost[i] >= 0; j--) {
// 可能性1: 不考虑当前主商品
// 可能性2: 考虑当前主商品，只要主
dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
fan1 = follows[i].size() >= 1 ? follows[i][0] : -1;
fan2 = follows[i].size() >= 2 ? follows[i][1] : -1;
// 可能性3: 主 + 附1
if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0)
dp[j] = max(dp[j], dp[j - cost[i] - cost[fan1]] + value[i] + value[fan1]);
// 可能性4: 主 + 附2
if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0)
dp[j] = max(dp[j], dp[j - cost[i] - cost[fan2]] + value[i] + value[fan2]);
// 可能性5: 主 + 附1 + 附2
if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0)
dp[j] = max(dp[j], dp[j - cost[i] - cost[fan1] - cost[fan2]] + value[i] + value[fan1] + value[fan2]);
}
}
cout << dp[n];
}
非负数组前k个最小的子序列累加和
非负数组前k个最小的子序列累加和
给定一个数组 nums，含有 n 个数字，都是非负数
给定一个正数 k，返回所有子序列中累加和最小的前 k 个累加和
子序列是包含空集的
1 <= n <= 10^5
1 <= nums[i] <= 10^6
1 <= k <= 10^5
注意这个数据量，用 01 背包的解法是不行的，时间复杂度太高了
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <random>
using namespace std;
// 非负数组前k个最小的子序列累加和
// 给定一个数组nums，含有n个数字，都是非负数
// 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
// 子序列是包含空集的
// 1 <= n <= 10^5
// 1 <= nums[i] <= 10^6
// 1 <= k <= 10^5
class Solution {
public:
// 暴力方法
vector<int> topKSum1(vector<int> &nums, int k) {
// 所有子序列的和
vector<int> allSubsequences;
recursive(nums, 0, 0, allSubsequences);
sort(allSubsequences.begin(), allSubsequences.end());
vector<int> res(k);
// 取前 k 个
for (int i = 0; i < k; i++)
res[i] = allSubsequences[i];
return res;
}
// 得到所有子序列的和
void recursive(vector<int> &nums, int curIndex, int sum, vector<int> &res) {
if (curIndex == nums.size()) {
res.push_back(sum);
return;
}
// 不要当前
recursive(nums, curIndex + 1, sum, res);
// 要当前
recursive(nums, curIndex + 1, sum + nums[curIndex], res);
}
// 01 背包来实现，时间复杂度太差，因为 n 很大，数值也很大，那么可能的累加和就更大
vector<int> topKSum2(vector<int> &nums, int k) {
int sum = 0;
for (int num: nums) sum += num;
vector<int> dp(sum + 1, 0);
dp[0] = 1;
for (int num: nums)
// 从右往左
for (int j = sum; j - num >= 0; j--)
dp[j] += dp[j - num];
vector<int> res(k);
int index = 0;
for (int j = 0; j <= sum && index < k; j++)
for (int i = 0; i < dp[j] && index < k; i++)
res[index++] = j;
return res;
}
struct cmp {
bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
return p1.second > p2.second;
}
};
// 正式方法
// 用堆来做是最优解，时间复杂度 O(n * log n) + O(k * log k)
vector<int> topKSum3(vector<int> &nums, int k) {
sort(nums.begin(), nums.end());
// <子序列的最右下标，子序列的累加和>，根据累加和递增
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
heap.push({0, nums[0]});
vector<int> res(k);
res[0] = 0;
for (int i = 1; i < k; i++) {
pair<int, int> cur = heap.top();
heap.pop();
int right = cur.first;
int sum = cur.second;
// 收集弹出的最小累加和
res[i] = sum;
if (right + 1 < nums.size()) {
// 去掉末尾，加上下个数
heap.push({right + 1, sum - nums[right] + nums[right + 1]});
// 不去掉末尾，加上下个数
heap.push({right + 1, sum + nums[right + 1]});
}
}
return res;
}
// 为了测试
vector<int> randomArray(int len, int value) {
vector<int> ans(len);
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(0, value);
for (int i = 0; i < len; i++)
ans[i] = dis(gen);
return ans;
}
// 为了测试
bool equals(const vector<int> &ans1, const vector<int> &ans2) {
if (ans1.size() != ans2.size()) return false;
for (int i = 0; i < ans1.size(); i++)
if (ans1[i] != ans2[i])
return false;
return true;
}
};
int main() {
Solution solution;
int n = 15;
int v = 40;
int testTime = 5000;
cout << "测试开始" << endl;
for (int i = 0; i < testTime; i++) {
int len = rand() % n + 1;
vector<int> nums = solution.randomArray(len, v);
int k = rand() % ((1 << len) - 1) + 1;
vector<int> ans1 = solution.topKSum1(nums, k);
vector<int> ans2 = solution.topKSum2(nums, k);
vector<int> ans3 = solution.topKSum3(nums, k);
if (!solution.equals(ans1, ans2) || !solution.equals(ans1, ans3))
cout << "出错了！" << endl;
}
cout << "测试结束" << endl;
}