当前位置: 首页 > article >正文

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的这个可变数组用处很大,其中一个就是可以用来存储列数不等的矩阵。

方法思路

  1. 预处理每个仓库的选项:对于每个仓库,计算所有可能的货物选择组合,并生成对应的费用和增益。增益为货物总价值减去仓库费用,费用包括基本费用和计件费用。

  2. 动态规划处理:使用动态规划来记录每个可能的增益对应的最小费用,通过遍历所有仓库的选项来更新状态,最终找到满足条件的最小费用。

注意点&知识点

  1. 为什么要从v开始遍历?这通常与背包问题中物品只能选一次的情况有关。比如0-1背包问题中,为了避免重复选取同一物品,需要逆序更新状态。这里类似,每个仓库的选项被视为一种“物品”,需要确保每个选项只被处理一次。因此,逆序遍历可以防止同一仓库的选项被多次累加,保证每次更新都是基于之前的状态。
  2. 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 的前提下,找到最小的总费用。


关键思路
  1. 仓库独立处理
    每个仓库的货物选择独立计算,最终通过动态规划组合所有仓库的选择。

  2. 预处理最优选项
    对每个仓库的货物进行排序和剪枝,生成有效选项:

    • 按净收益排序:对货物按 a_i - c_j 降序排列,优先选择净收益高的货物。

    • 剪枝无效选项:保留费用递增时收益严格递增的选项,去除费用高但收益低的组合。

  3. 动态规划状态转移

    • 状态定义dp[g] 表示达到收益 g 所需的最小费用。

    • 转移方式:倒序遍历收益值,避免重复计算同一仓库的选项。

    • 收益截断:超过 v 的收益统一视为 v,简化计算。

复杂度分析
  • 预处理阶段
    每个仓库的货物排序和剪枝的时间复杂度为 O(m log m),总复杂度为 O(n m log m)

  • 动态规划阶段
    每个仓库的选项数为 O(m),每次转移的时间复杂度为 O(v),总复杂度为 O(n m v)


关键优化点
  1. 剪枝策略
    仅保留费用递增时收益严格递增的选项,减少无效状态转移。

  2. 倒序更新
    避免同一仓库的选项被多次累加,确保状态转移正确性。

  3. 收益截断
    将超过 v 的收益视为 v,压缩状态空间,提升效率。


总结

通过预处理生成每个仓库的有效选项,结合动态规划的组合优化,能够高效解决此问题。核心在于合理剪枝和状态转移设计,确保在较大规模数据下的可行性。


http://www.kler.cn/a/589218.html

相关文章:

  • 零基础使用鸿蒙NDK开发最简步骤
  • KVM安全模块生产环境配置与优化指南
  • 【模拟面试】计算机考研复试集训(第四天)
  • 工程化与框架系列(35)--前端微服务架构实践
  • 【2025年39期免费获取股票数据API接口】实例演示五种主流语言获取股票行情api接口之沪深指数最新分时MACD数据获取实例演示及接口API说明文档
  • Spring 扩展点总结与分析
  • 【论文笔记】FFA-Net: Feature Fusion Attention Network for Single Image Dehazing
  • Spring MVC源码分析の请求处理流程
  • 从过拟合到强化学习:机器学习核心知识全解析
  • R 语言科研绘图 --- 密度图-汇总
  • C/C++基数排序(Radix Sort) 的排序算法。
  • 深入理解TCP/IP网络模型及Linux网络管理
  • Solidity基础 -- 哈希算法
  • C++ QT零基础教学(二)
  • tomato靶场通关攻略
  • Leetcode-131.Palindrome Partitioning [C++][Java]
  • ST的全新STM32U3微控制器(MCU)简析
  • 视频推拉流EasyDSS案例分析:互联网直播/点播技术与平台创新应用
  • 【PyTorch教学】pytorch 基本语法
  • 消息队列 Kafka、RocketMQ、RabbitMQ 对比与分析