数据结构与算法 / 系统课时

从业务需求抽象算法问题

从业务需求抽象算法问题

业务需求通常混合目标、限制和口语化假设。本课以“有限时间内优先处理高价值工单”为例,把一句需求拆成输入、输出、约束和验收条件,并落成可测试的算法接口。

学习目标

  • 识别需求中的目标函数、输入数据和硬约束
  • 将自然语言描述转换为可验证的问题模型
  • 通过接口契约、样例与边界条件检查模型是否完整

先找出真正的问题

原始需求可以表述为:“客服只有 8 分钟,希望处理优先级最高的一组工单。”这句话还不能直接编码,因为“优先级最高”可能指单个工单优先级,也可能指所选工单的总优先级;“处理”还可能允许中途暂停。

建模前应确认四类信息:

  • 输入:每个工单的处理时间和优先级分数。
  • 输出:在总时间限制内可获得的最大优先级总分。
  • 约束:每个工单只能完整处理一次,不能拆分,也不能重复选择。
  • 验收:给定固定样例时结果唯一可核对,非法输入能够被拒绝。

从业务需求到算法模型的转换流程

建立可验证的问题模型

设第 ii 个工单的处理时间为 cic_i,优先级为 viv_i,总可用时间为 TT。用 xix_i 表示是否选择该工单,其中 xi∈{0,1}x_i \in \{0,1\}。模型为:

max⁡∑i=1nvixi\max \sum_{i=1}^{n} v_i x_i

并满足:

∑i=1ncixi≤T\sum_{i=1}^{n} c_i x_i \le T

这个模型明确了“总优先级最大”是目标,“总处理时间不超过上限”是硬约束,而 xix_i 只能取 0 或 1,说明工单不可拆分。因此它对应 0/1 背包模型,而不是允许按比例选择的分数背包模型。

模型元素 业务含义 验证方式
cic_i 第 ii 个工单的完整处理时间 必须为正整数
viv_i 第 ii 个工单的优先级分数 必须为非负整数
TT 当前可用总时间 必须为非负整数
xix_i 是否完整选择第 ii 个工单 只能取 0 或 1
目标值 所选工单的优先级总和 与固定样例结果比较

边界条件也属于模型的一部分:空工单列表应返回 0;时间上限为 0 时只能选择成本为 0 的任务,但本例禁止成本为 0,因此结果为 0;数组长度不一致、负时间或负优先级都应视为非法输入。

设计算法接口

接口应只暴露业务需要的输入和结果,不泄漏动态规划数组等实现细节。本例使用 maximizePriority(int[] timeCosts, int[] priorities, int totalMinutes),返回可获得的最大优先级总分。

接口契约包括:

  • timeCosts[i] 与 priorities[i] 必须描述同一个工单。
  • 两个数组不得为 null 且长度相同。
  • totalMinutes 不得为负数。
  • 方法不修改传入数组,没有外部副作用。
  • 返回值只表示最优总分,不负责决定工单的实际执行顺序。

完整可运行示例

下面的 Java 17 程序使用一维动态规划实现该接口。时间维度从大到小遍历,保证每个工单最多被选择一次。

java
public class RequirementModelDemo {

    public static int maximizePriority(
            int[] timeCosts,
            int[] priorities,
            int totalMinutes) {

        if (timeCosts == null || priorities == null) {
            throw new IllegalArgumentException("输入数组不能为 null");
        }
        if (timeCosts.length != priorities.length) {
            throw new IllegalArgumentException("处理时间与优先级数量必须一致");
        }
        if (totalMinutes < 0) {
            throw new IllegalArgumentException("总时间不能为负数");
        }

        // dp[t] 表示时间上限为 t 时能够获得的最大优先级总分。
        int[] dp = new int[totalMinutes + 1];

        for (int i = 0; i < timeCosts.length; i++) {
            int cost = timeCosts[i];
            int score = priorities[i];

            if (cost <= 0 || score < 0) {
                throw new IllegalArgumentException("处理时间必须为正数,优先级不能为负数");
            }

            // 倒序更新,避免同一个工单在一轮中被重复使用。
            for (int t = totalMinutes; t >= cost; t--) {
                dp[t] = Math.max(dp[t], dp[t - cost] + score);
            }
        }

        return dp[totalMinutes];
    }

    public static void main(String[] args) {
        int[] timeCosts = {2, 3, 4, 5};
        int[] priorities = {3, 4, 8, 10};
        int totalMinutes = 8;

        int result = maximizePriority(timeCosts, priorities, totalMinutes);
        System.out.println("最大优先级得分: " + result);
    }
}

将代码保存为 RequirementModelDemo.java,然后执行:

bash
javac RequirementModelDemo.java
java RequirementModelDemo

预期输出

text
最大优先级得分: 14

结果 14 来自选择处理时间为 3 和 5 分钟的两个工单。它们正好占满 8 分钟,优先级总分为 4 加 10。

常见错误

  • 把目标写成“先处理最高优先级工单”:这会变成局部贪心规则,不能保证总分最优。正确做法是明确优化整个选择集合的总分。
  • 遗漏“工单不可拆分”:一旦允许拆分,问题模型和算法都会改变。需求评审时必须把可分割性写入约束。
  • 接口只描述正常输入:数组长度不一致或出现负数时行为不明确,会让调用方得到难以定位的错误。应在接口入口集中校验。

本课练习

  1. 将“仓库车辆每天最多行驶 120 公里,希望完成总收益最高的一组配送任务”建模。写出输入、输出、目标函数、约束和至少三个边界条件,验收标准是模型能够区分任务可拆分与不可拆分两种情况。
  2. 为本课接口增加“返回被选工单下标”的需求说明。只设计返回结构、异常规则和验收样例,不要求实现算法;验收时应能说明多个最优解并存时采用哪种稳定规则。

本课总结

  • 业务句子必须被拆成输入、输出、目标、约束和验收条件后才能可靠编码。
  • 数学模型用于消除歧义,接口契约用于固定模型在程序中的边界。
  • 样例与异常输入不是补充材料,而是验证需求抽象是否完整的直接证据。

下一课预告

下一课将学习“算法与数据结构选型”,在问题模型已经明确的前提下,根据数据规模、操作频率、内存和实时性要求选择可落地的实现方案。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

从业务需求抽象算法问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通