CCF-CSP第34次认证第四题——货物调度【DP+剪枝】

CCF-CSP第34次认证第四题——货物调度

官网链接：TUOJ

题解

思考过程

1. 题目要求的是“在满足总现金【即收益：卖出的货物总价值减去总费用的结果】至少为v的前提下，需要的最小的总费用”

2. 也就是说我们要求的有两个，一个是收益，一个是费用，所以我们考虑对每个仓库分别进行计算，预处理每个仓库可能的<收益，费用>组合，再遍历这些组合来寻找最优解——其实也不是所有可能的<收益，费用>组合，我们只要找收益最大的就行了，所以可以先给每个货物的收益【价值a - 计件费用c】排序，从大的开始加，使用前缀和数组存这个结果，最优解一定在这些组合里——所以我们需要自定义一个比较函数来实现我们想要的排序【这里涉及Lambda 表达式的使用，大家可以搜一下它的简单用法】

- 补充内容：

sort(g.begin(), g.end(), [c](int a, int b) {return a - c > b - c}); //记住排序函数是返回true的话就按参数传入的顺序排

记住排序函数是返回true就按参数传入的顺序排，意思就是这里传入顺序是ab，如果返回true的话，排序的结果就是a在b的前面

3. 货物的存储很重要，因为每个仓库里货物的数量不一致，并且货物有两个属性，一个t对应第几间仓库，一个a对应货物价值，如果使用pair的话虽然能存两个相关信息，但是有一个很重要的关联就被忽略了，即我们不能找出同一间仓库的所有货物

为了能找出同一间仓库的所有货物，考虑其他存储结构，能不能用map呢——不能，因为map 不能存储多个相同的 key，即 key 具有唯一性。如果尝试插入相同的 key，新值会覆盖旧值，可以考虑使用multimap，但是没必要，其实直接用vector数组就行了，STL的这个可变数组用处很大，其中一个就是可以用来存储列数不等的矩阵。

方法思路

预处理每个仓库的选项：对于每个仓库，计算所有可能的货物选择组合，并生成对应的费用和增益。增益为货物总价值减去仓库费用，费用包括基本费用和计件费用。
动态规划处理：使用动态规划来记录每个可能的增益对应的最小费用，通过遍历所有仓库的选项来更新状态，最终找到满足条件的最小费用。

注意点&知识点

为什么要从v开始遍历？这通常与背包问题中物品只能选一次的情况有关。比如0-1背包问题中，为了避免重复选取同一物品，需要逆序更新状态。这里类似，每个仓库的选项被视为一种“物品”，需要确保每个选项只被处理一次。因此，逆序遍历可以防止同一仓库的选项被多次累加，保证每次更新都是基于之前的状态。
prev_dp保存了之前所有仓库处理后的状态，每次处理新的仓库选项时，基于之前的状态进行更新，这样可以避免覆盖当前轮次的数据，确保每次更新都是基于正确的旧值。

参考题解

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>using namespace std;const int INF = 1e9;typedef pair<int, int> PII; int main () {int n, m, v;scanf("%d%d%d", &n, &m, &v);PII store_bc[n];int first, second; for(int i = 0; i < n; i++) {scanf("%d%d", &store_bc[i].first, &store_bc[i].second);}vector<vector<int> > goods(n);for(int i = 0; i < m; i++) {int a, t;scanf("%d%d", &a, &t);goods[t].push_back(a);}vector<vector<PII> > all_options; //存储n间仓库的<费用,收益>组合，每一间的是一个PII数组 for(int i = 0; i < n; i++) {int b = store_bc[i].first, c = store_bc[i].second;vector<int>& g = goods[i]; //使用引用，避免了复制操作的开销sort(g.begin(), g.end(), [c](int a, int b) {return a - c > b - c;}); //记住排序函数是返回true的话排就按参数传入的顺序排 int sum = 0; //用于存储总收益vector<int> prefix;for(auto &a : g) {sum += a - c;prefix.push_back(sum);} vector<PII> options;for(int j = 0; j < prefix.size(); j++) {options.emplace_back(b + c * (j + 1), prefix[j] - b); //先存费用，因为要选费用最小的 }sort(options.begin(), options.end()); //按费用排序 //为了减少后面的复杂度，这里可以提前进行相关判断----剪枝 vector<PII> pruned;int max_gain = -INF;for(auto& opt : options) {if(opt.second > max_gain) { //因为是按费用升序排的，只有当收益大于前面的收益时才有可能会做出这个选择，否则不可能是最优解 pruned.push_back(opt);max_gain = opt.second;}}all_options.push_back(pruned);} vector<int> dp(v + 1, INF); //dp[i]：存储收益为i时的费用j dp[0] = 0;for(auto& options : all_options) { //每间仓库的可能选择组合 vector<int> prev_dp = dp;for(auto& opt : options) { //当前仓库的每个可能选择 int cost = opt.first, gain = opt.second;for(int g = v; g >= 0; g--) {if(prev_dp[g] != INF) {int new_g = min(g + gain, v); //如果超过v了就存v就行，因为最终只要求输出costif(new_g >= 0) {if(dp[new_g] > prev_dp[g] + cost) {dp[new_g] = prev_dp[g] + cost; //出现了更优解就更新dp } }}}} } printf("%d\n", dp[v]); return 0;
}

总结

DP问题比较难想，还是得多做题积累经验

问题总结：货物调度问题

核心目标

在满足总收益（货物价值总和 - 仓库费用）至少为 v 的前提下，找到最小的总费用。

关键思路

仓库独立处理
每个仓库的货物选择独立计算，最终通过动态规划组合所有仓库的选择。
预处理最优选项
对每个仓库的货物进行排序和剪枝，生成有效选项：
- 按净收益排序：对货物按 a_i - c_j 降序排列，优先选择净收益高的货物。
- 剪枝无效选项：保留费用递增时收益严格递增的选项，去除费用高但收益低的组合。
动态规划状态转移
- 状态定义：dp[g] 表示达到收益 g 所需的最小费用。
- 转移方式：倒序遍历收益值，避免重复计算同一仓库的选项。
- 收益截断：超过 v 的收益统一视为 v，简化计算。