数据结构与算法 / 系统课时
从业务需求抽象算法问题
从业务需求抽象算法问题
业务需求通常混合目标、限制和口语化假设。本课以“有限时间内优先处理高价值工单”为例,把一句需求拆成输入、输出、约束和验收条件,并落成可测试的算法接口。
学习目标
- 识别需求中的目标函数、输入数据和硬约束
- 将自然语言描述转换为可验证的问题模型
- 通过接口契约、样例与边界条件检查模型是否完整
先找出真正的问题
原始需求可以表述为:“客服只有 8 分钟,希望处理优先级最高的一组工单。”这句话还不能直接编码,因为“优先级最高”可能指单个工单优先级,也可能指所选工单的总优先级;“处理”还可能允许中途暂停。
建模前应确认四类信息:
- 输入:每个工单的处理时间和优先级分数。
- 输出:在总时间限制内可获得的最大优先级总分。
- 约束:每个工单只能完整处理一次,不能拆分,也不能重复选择。
- 验收:给定固定样例时结果唯一可核对,非法输入能够被拒绝。

建立可验证的问题模型
设第 个工单的处理时间为 ,优先级为 ,总可用时间为 。用 表示是否选择该工单,其中 。模型为:
并满足:
这个模型明确了“总优先级最大”是目标,“总处理时间不超过上限”是硬约束,而 只能取 0 或 1,说明工单不可拆分。因此它对应 0/1 背包模型,而不是允许按比例选择的分数背包模型。
| 模型元素 | 业务含义 | 验证方式 |
|---|---|---|
| 第 个工单的完整处理时间 | 必须为正整数 | |
| 第 个工单的优先级分数 | 必须为非负整数 | |
| 当前可用总时间 | 必须为非负整数 | |
| 是否完整选择第 个工单 | 只能取 0 或 1 | |
| 目标值 | 所选工单的优先级总和 | 与固定样例结果比较 |
边界条件也属于模型的一部分:空工单列表应返回 0;时间上限为 0 时只能选择成本为 0 的任务,但本例禁止成本为 0,因此结果为 0;数组长度不一致、负时间或负优先级都应视为非法输入。
设计算法接口
接口应只暴露业务需要的输入和结果,不泄漏动态规划数组等实现细节。本例使用 maximizePriority(int[] timeCosts, int[] priorities, int totalMinutes),返回可获得的最大优先级总分。
接口契约包括:
timeCosts[i]与priorities[i]必须描述同一个工单。- 两个数组不得为
null且长度相同。 totalMinutes不得为负数。- 方法不修改传入数组,没有外部副作用。
- 返回值只表示最优总分,不负责决定工单的实际执行顺序。
完整可运行示例
下面的 Java 17 程序使用一维动态规划实现该接口。时间维度从大到小遍历,保证每个工单最多被选择一次。
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,然后执行:
javac RequirementModelDemo.java
java RequirementModelDemo预期输出
最大优先级得分: 14结果 14 来自选择处理时间为 3 和 5 分钟的两个工单。它们正好占满 8 分钟,优先级总分为 4 加 10。
常见错误
- 把目标写成“先处理最高优先级工单”:这会变成局部贪心规则,不能保证总分最优。正确做法是明确优化整个选择集合的总分。
- 遗漏“工单不可拆分”:一旦允许拆分,问题模型和算法都会改变。需求评审时必须把可分割性写入约束。
- 接口只描述正常输入:数组长度不一致或出现负数时行为不明确,会让调用方得到难以定位的错误。应在接口入口集中校验。
本课练习
- 将“仓库车辆每天最多行驶 120 公里,希望完成总收益最高的一组配送任务”建模。写出输入、输出、目标函数、约束和至少三个边界条件,验收标准是模型能够区分任务可拆分与不可拆分两种情况。
- 为本课接口增加“返回被选工单下标”的需求说明。只设计返回结构、异常规则和验收样例,不要求实现算法;验收时应能说明多个最优解并存时采用哪种稳定规则。
本课总结
- 业务句子必须被拆成输入、输出、目标、约束和验收条件后才能可靠编码。
- 数学模型用于消除歧义,接口契约用于固定模型在程序中的边界。
- 样例与异常输入不是补充材料,而是验证需求抽象是否完整的直接证据。
下一课预告
下一课将学习“算法与数据结构选型”,在问题模型已经明确的前提下,根据数据规模、操作频率、内存和实时性要求选择可落地的实现方案。