【大厂机试题解法笔记】高效货运
老李是货运公司承运人，老李的货车额定载货重量为 wt。
现有两种货物：
- 货物 A 单件重量为 wa，单件运费利润为 pa
- 货物 B 单件重量为 wb，单件运费利润为 pb
老李每次发车时载货总重量刚好为货车额定的载货重量 wt，车上必须同时有货物 A 和货物 B ，货物A、B不可切割。
老李单次满载运输可获得的最高利润是多少？
输入描述
- 第一列输入为货物 A 的单件重量 wa ，0 < wa < 10000
- 第二列输入为货物 B 的单件重量 wb,0 < wb < 10000
- 第三列输入为货车的额定载重 wt,0 < wt < 100000
- 第四列输入为货物 A 的单件运费利润 pa,0 < pa < 1000
- 第五列输入为货物 B 的单件运费利润 pb,0 < pb < 1000
输出描述
单次满载运输的最高利润
用例
| 输入 | 输出 |
|---|---|
| 10 8 36 15 7 | 44 |
| 1 1 2 1 1 | 2 |
思考
总结题意：x > 0, y > 0, x * wa + y * wb = wt，x 和 y 分别表示货物 A 和 货物 B 的数量，求怎么分配 x 和 y 从而使 x * pa + y * pb 最大。我觉得就是解二元一次方程，而且解（x、y）必须是正整数。设 f(x, y) = x * pa + y * pb ，因为 y = (wt - x * wa) / wb，所以 f(x, y) 转为一元一次方程：f(x) = pa * x + (wt - x * wa) / wb * pb = (pa - pb * wa / wb ) * x + pb * wt / wb。这个方程是一条直线，斜率 k = (pa - pb * wa / wb )， 根据 k 的正负可知 f(x) 是单调性。如果 k > =0，f (x) 单调递增（包括平行 x 轴），则 x 从 1 开始枚举，x 取值范围在 [1, Math.floor((wt - wb)/wa ]，Math.floor((wt - wb)/wa 表示除去一个货物 B 的剩余载货空间下货物 A 能装载的最大数量。对于单调递增的情形，x 从最大值往最小值1枚举，每次计算对应的 y 值，如果y值是小数跳过继续迭代，直到找到 x 和 y 都是正整数，此时的 f(x) 最大，即满载货物 A 和 货物 B 的利润最大。对于 k < 0，单调递减函数的计算类似。记得初中数学课学过线性优化问题，这个题目应该就可以转化为线性优化问题。这种遍历枚举的方式比直接从1开始暴力枚举更新全局最大利润要好。 题目描述“老李每次发车时载货总重量刚好为货车额定的载货重量”应该表示输入数据不存在无解的情况，因此不需要考虑 x * wa + y * wb != wt 的无解情形。
算法思路
1. 问题建模与数学转化
- 目标：在货车满载（总重量为
wt）且同时装载货物 A 和 B 的条件下，最大化运输利润。 - 变量定义：
- x：货物 A 的数量（\(x > 0\)，整数）
- y：货物 B 的数量（\(y > 0\)，整数）
- 约束条件：\(x \cdot wa + y \cdot wb = wt\)
- 利润函数：\(f(x, y) = x \cdot pa + y \cdot pb\)
- 转化为一元函数：将 \(y = \frac{wt - x \cdot wa}{wb}\) 代入利润函数，得：\(f(x) = \left( pa - \frac{pb \cdot wa}{wb} \right) x + \frac{pb \cdot wt}{wb}\)
2. 单调性分析与枚举策略
-
斜率计算：定义斜率 \(k = pa - \frac{pb \cdot wa}{wb}\)，用于判断函数单调性：
- 若 \(k \geq 0\)，\(f(x)\) 随 x 增大而递增，应优先取最大可能的 x；
- 若 \(k < 0\)，\(f(x)\) 随 x 增大而递减，应优先取最小可能的 x。
-
枚举范围确定：
- x 的最大值：\(\text{maxA} = \left\lfloor \frac{wt - wb}{wa} \right\rfloor\)（至少留 1 个 B 的重量，即 \(y \geq 1\)）；
- x 的最小值：1（至少 1 个 A）。
3. 整数解筛选与利润计算
-
递增情况（\(k \geq 0\)）： 从 \(x = \text{maxA}\) 倒序枚举至 \(x = 1\)，对每个 x 检查：\((wt - x \cdot wa) \% wb === 0\) 若成立，则 \(y = \frac{wt - x \cdot wa}{wb}\) 为整数，计算当前利润 \(f(x, y)\) 并返回（因函数递增，首个有效解即为最大值）。
-
递减情况（\(k < 0\)）： 从 \(x = 1\) 顺序枚举至 \(x = \text{maxA}\)，对每个 x 检查同上条件，首个有效解即为最大值（因函数递减，最小 x 对应最大利润）。
4. 算法复杂度分析
- 时间复杂度：最坏情况下需枚举 \(O(\frac{wt}{wa})\) 次，其中 \(wt < 10^5\)，\(wa > 0\)，故复杂度为 \(O(10^5)\)，可高效求解。
- 空间复杂度：仅使用常数级变量（\(x, y, k\) 等），复杂度为 \(O(1)\)。
参考代码
function solution() {const [wa, wb, wt, pa, pb] = readline().split(' ').map(Number);const k = pa - pb * wa / wb;// console.log("k: ", k);const maxA = Math.floor((wt-wb)/wa);// console.log('maxA: ', maxA);if (k >= 0) {for (let i = maxA; i >= 1; i--) {if ((wt - i*wa) % wb === 0) {console.log(i * pa + (wt - i*wa) / wb * pb);return;}}} for (let i = 1; i <= maxA; i++) {if ((wt - i*wa) % wb === 0) {console.log(i * pa + (wt - i*wa) / wb * pb);return;}}}const cases = [`10 8 36 15 7`,`1 1 2 1 1`
];let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});