首页 > 试题广场 >

加速优化问题

[编程题]加速优化问题

热度指数：77 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

某物流公司需要为一条运输线路上的多个中转段选择运输方案。整条线路由若干个中转段组成，每个中转段可以选择不同的运输方式（如空运、陆运等），不同方式的运费和延误风险各不相同。

公司的目标是在保证总延误风险不超过给定阈值的前提下，使得整条线路的总运费最低。

具体条件如下：每个中转段在不同运输方式下有各自的延误风险值（浮点数）和运费（浮点数）。每个中转段必须且只能选择一种运输方式。所有中转段的延误风险之和不能超过阈值 T。

请设计算法，为每个中转段选择最优的运输方式，使得总运费最小且满足总延误风险不超过 T。

输入描述:

第一行：整数 L（中转段数量）和浮点数 T（延误风险阈值）。
接下来 L 行，每行描述一个中转段的可选方案：先是一个整数 K（该中转段可选的运输方式数量），随后是 K 组数据，每组包含：方式名称（字符串）、延误风险（浮点数）、运费（浮点数）。

输出描述:

输出最优总运费（保留两位小数）。

示例1

输入

2 0.4
2 express 0.1 300.0 standard 0.25 120.0
2 express 0.05 250.0 standard 0.2 100.0

输出

370.00

说明

2 个中转段，延误风险阈值为 0.4。
枚举所有组合：
(1) express+express：风险 0.1+0.05=0.15，运费 300+250=550
(2) express+standard：风险 0.1+0.2=0.3，运费 300+100=400
(3) standard+express：风险 0.25+0.05=0.3，运费 120+250=370
(4) standard+standard：风险 0.25+0.2=0.45 > 0.4，不可行
满足约束的方案中，最小运费为方案(3)的 370。

示例2

输入

3 0.5
1 ground 0.15 80.0
2 air 0.1 200.0 ground 0.3 90.0
2 air 0.05 180.0 ground 0.2 70.0

输出

350.00

说明

3 个中转段，延误风险阈值为 0.5。第一段只有 ground 可选（风险 0.15，运费 80）。
可行方案：
(1) ground+ground+air：风险 0.15+0.3+0.05=0.5，运费 80+90+180=350
(2) ground+air+ground：风险 0.15+0.1+0.2=0.45，运费 80+200+70=350
(3) ground+air+air：风险 0.15+0.1+0.05=0.3，运费 80+200+180=460
ground+ground+ground 风险 0.65 超出阈值，不可行。
最小运费为 350。