题解 | #加速优化问题#

题目链接

题目描述

某物流公司需要为包含 $L$ 个中转段的运输线路选择最优方案。每个中转段有 $K$ 种可选的运输方式，每种方式对应一个延误风险值（浮点数）和运费（浮点数）。要求在满足总延误风险不超过阈值 $T$ 的前提下，为每个中转段选择一种运输方式，使得整条线路的总运费最低。

解题思路

本题是分组背包问题的一个变种，其中物品的重量和价值均为浮点数，且目标是最小化总价值（运费）并满足总重量（风险）限制。

状态定义：由于风险值是浮点数，传统的以风险为下标的数组 DP 无法直接使用。我们可以使用一个映射表 $dp$ 来存储状态，其中 $dp[r]$ 表示总延误风险为 $r$ 时的最小总运费。
动态规划过程：
- 初始化 $dp$ 字典，初始状态为 $\{0.0: 0.0\}$ ，表示风险为 $0$ 时运费为 $0$ 。
- 遍历每一个中转段：
  - 创建一个新的映射表 $new\_dp$ 。
  - 遍历当前中转段的所有可选运输方式 $(risk, cost)$ 。
  - 对于 $dp$ 中的每一个已有状态 $(total\_risk, total\_cost)$ ：
    - 计算新的总风险 $r_{new} = total\_risk + risk$ 和总运费 $c_{new} = total\_cost + cost$ 。
    - 如果 $r_{new} \le T$ ，则尝试更新 $new\_dp[r_{new}]$ 为 $\min(new\_dp[r_{new}], c_{new})$ 。
  - 将 $dp$ 更新为 $new\_dp$ 。
优化建议：
- 如果状态数过多，可以对 $dp$ 中的状态进行剪枝。如果存在两个状态 $(r_1, c_1)$ 和 $(r_2, c_2)$ ，满足 $r_1 \le r_2$ 且 $c_1 \le c_2$ ，那么状态 $(r_2, c_2)$ 是被支配的，可以舍弃。
- 考虑到浮点数精度问题，比较风险总和与 $T$ 时可以加入一个极小值 $\epsilon$ （如 $10^{-9}$ ）。
结果输出：遍历最终 $dp$ 映射表中的所有值，找到最小的运费，并按要求保留两位小数输出。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <iomanip>

using namespace std;

// 使用 map 存储风险到最小运费的映射，map 会自动按风险排序
// dp[risk] = min_cost
int main() {
    int l;
    double t_threshold;
    cin >> l >> t_threshold;

    map<double, double> dp;
    dp[0.0] = 0.0;

    for (int i = 0; i < l; ++i) {
        int k;
        cin >> k;
        map<double, double> next_dp;
        for (int j = 0; j < k; ++j) {
            string name;
            double risk, cost;
            cin >> name >> risk >> cost;
            for (auto const& [total_risk, total_cost] : dp) {
                double new_risk = total_risk + risk;
                double new_cost = total_cost + cost;
                // 考虑浮点数精度，使用微小偏移量
                if (new_risk <= t_threshold + 1e-9) {
                    if (next_dp.find(new_risk) == next_dp.end() || new_cost < next_dp[new_risk]) {
                        next_dp[new_risk] = new_cost;
                    }
                }
            }
        }
        // 剪枝优化：去掉被支配的状态
        if (next_dp.empty()) {
            // 如果某一段无法选出满足风险限制的方案，则后续也无法完成
            dp.clear();
            break;
        }
        
        dp.clear();
        double min_cost_so_far = -1.0;
        for (auto const& [r, c] : next_dp) {
            if (min_cost_so_far < 0 || c < min_cost_so_far) {
                dp[r] = c;
                min_cost_so_far = c;
            }
        }
    }

    double ans = -1.0;
    for (auto const& [r, c] : dp) {
        if (ans < 0 || c < ans) ans = c;
    }

    cout << fixed << setprecision(2) << ans << endl;

    return 0;
}

import java.util.*;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.math.RoundingMode;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        double tThreshold = sc.nextDouble();

        // TreeMap 存储风险到最小运费的映射，风险升序排列
        TreeMap<Double, Double> dp = new TreeMap<>();
        dp.put(0.0, 0.0);

        for (int i = 0; i < l; i++) {
            int k = sc.nextInt();
            // 存储当前段所有可能的组合结果
            TreeMap<Double, Double> nextDp = new TreeMap<>();
            
            for (int j = 0; j < k; j++) {
                String name = sc.next();
                double risk = sc.nextDouble();
                double cost = sc.nextDouble();

                for (Map.Entry<Double, Double> entry : dp.entrySet()) {
                    double newRisk = entry.getKey() + risk;
                    double newCost = entry.getValue() + cost;
                    // 阈值检查，考虑浮点误差
                    if (newRisk <= tThreshold + 1e-11) {
                        if (!nextDp.containsKey(newRisk) || newCost < nextDp.get(newRisk)) {
                            nextDp.put(newRisk, newCost);
                        }
                    }
                }
            }

            if (nextDp.isEmpty()) {
                dp.clear();
                break;
            }

            // 支配性剪枝：只保留风险增加且运费减少的状态
            dp = new TreeMap<>();
            double minCostSoFar = Double.MAX_VALUE;
            for (Map.Entry<Double, Double> entry : nextDp.entrySet()) {
                // 如果当前状态的运费比之前所有风险更小的状态都小，则保留
                if (entry.getValue() < minCostSoFar - 1e-11) {
                    dp.put(entry.getKey(), entry.getValue());
                    minCostSoFar = entry.getValue();
                }
            }
        }

        double minAns = Double.MAX_VALUE;
        for (double cost : dp.values()) {
            if (cost < minAns) minAns = cost;
        }

        if (minAns == Double.MAX_VALUE) return;
        
        // 使用 DecimalFormat 强制输出两位小数且采用 HALF_EVEN 模式（与 Python 保持一致）
        DecimalFormat df = new DecimalFormat("0.00");
        df.setRoundingMode(RoundingMode.HALF_EVEN);
        DecimalFormatSymbols symbols = new DecimalFormatSymbols(Locale.US);
        df.setDecimalFormatSymbols(symbols);
        System.out.println(df.format(minAns));
    }
}

def solve():
    import sys
    
    # 读取第一行 L 和 T
    line = input().split()
    l_count = int(line[0])
    t_threshold = float(line[1])
    
    # dp 存储 {风险: 最小运费}
    dp = {0.0: 0.0}
    
    for _ in range(l_count):
        data = input().split()
        k = int(data[0])
        next_dp = {}
        
        # 解析该段的所有方式
        methods = []
        idx = 1
        for _ in range(k):
            name = data[idx]
            risk = float(data[idx + 1])
            cost = float(data[idx + 2])
            methods.append((risk, cost))
            idx += 3
            
        for risk, cost in methods:
            for total_risk, total_cost in dp.items():
                new_risk = total_risk + risk
                new_cost = total_cost + cost
                if new_risk <= t_threshold + 1e-9:
                    if new_risk not in next_dp or new_cost < next_dp[new_risk]:
                        next_dp[new_risk] = new_cost
        
        if not next_dp:
            dp = {}
            break
            
        # 剪枝优化：按风险排序后，只保留运费随风险增加而减少的状态
        sorted_keys = sorted(next_dp.keys())
        dp = {}
        min_cost_so_far = float('inf')
        for r in sorted_keys:
            if next_dp[r] < min_cost_so_far:
                dp[r] = next_dp[r]
                min_cost_so_far = next_dp[r]
                
    if not dp:
        # 如果题目保证有解，此行通常不会执行
        return

    ans = min(dp.values())
    print(format(ans, ".2f"))

solve()

算法及复杂度

算法：分组背包问题（浮点数版）+ 状态支配剪枝。
时间复杂度： $\mathcal{O}(L \cdot K \cdot S)$ 。其中 $L$ 为中转段数量， $K$ 为平均运输方式数量， $S$ 是每一轮保留的有效状态数。由于剪枝的存在， $S$ 的规模通常远小于所有可能组合。
空间复杂度： $\mathcal{O}(S)$ 。需要存储当前轮次和下一轮次的有效状态。