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就行,因为最终只要求输出cost
if(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
,简化计算。
-
复杂度分析
-
预处理阶段:
每个仓库的货物排序和剪枝的时间复杂度为O(m log m)
,总复杂度为O(n m log m)
。 -
动态规划阶段:
每个仓库的选项数为O(m)
,每次转移的时间复杂度为O(v)
,总复杂度为O(n m v)
。
关键优化点
-
剪枝策略
仅保留费用递增时收益严格递增的选项,减少无效状态转移。 -
倒序更新
避免同一仓库的选项被多次累加,确保状态转移正确性。 -
收益截断
将超过v
的收益视为v
,压缩状态空间,提升效率。
总结
通过预处理生成每个仓库的有效选项,结合动态规划的组合优化,能够高效解决此问题。核心在于合理剪枝和状态转移设计,确保在较大规模数据下的可行性。