租船问题有哪些（没人比我更懂租船）

很荣幸，网上有数学老师邀请我解答一个问题——

春游时，全班38人要坐船游玩，每只大船可以坐10个人，租金为90元；每只小船可以坐4人，租金为40元，那么应该租几只大船几只小船才能使总花费最少？

网上某老师提问

【序】

既然是老师提问，就不能只讲这一道题怎么做，而是深入讲一讲这一类题怎么做，或是这一种数学模型有何特征，有何通用解决方案.

以下是我的尝试，虽然有些标题党嫌疑，但仍希望能让大家对这类租船问题有一种全新的认识.

【思路】

1. 本题是多个约束条件下对大船数x与小船数y在自然数范围内寻求最优方案[1]的应用题；
2. 本题在小学阶段我们更多采用枚举法[2]尝试；
3. 枚举前应先确定枚举类型[3]和枚举方向[4]；
4. 确定枚举类型的依据是船的理论人均花费[5]，理论人均花费较少者为枚举对象；
5. 为了让总花费最少，要尽可能多用理论人均花费少的船只，所以枚举方向应是从多到少；
6. 如果理论人均花费少的那类船全都坐满[6]，就已经达到总花费最优；
7. 如果最后一艘船没有坐满，且最后一艘船的实际人均花费[7]大于另一类船的理论人均花费时，应当继续枚举，不断减少理论人均花费少的船只数量，并相应增加另一类船只数量；
8. 直到首次出现两类船的每一艘都坐满[8]，代入此时的x、y即可求出最少总花费.

【步骤】

以人均花费为依据的枚举解题步骤

【讲解】

1. 大船租金90元，大船可坐10人，大船理论人均花费：90÷10=9（元/人），括号内单位这样写是为了提醒同学们这个9元是“人均”；小船租金40元，小船可坐4人，小船理论人均花费：40÷4=10（元/人）；由于大船的人均9元/人小于小船的人均10元/人，所以我们应该尽量使用大船；
2. 38人除以10人等于3整艘大船余8人，所以最多租4艘大船，此时总花费：90×4=360（元）；
3. 但最多可坐10人的第4艘大船只坐了8人，该艘大船的实际人均花费为：90÷8=11.25（元/人），这个人均11.25元已经大于了小船的理论人均10元，说明如果把这8人放在若干小船上并坐满，是比租一艘大船更划算的；
4. 而如果租3艘大船，剩余8人租小船：8÷4=2（艘），总花费：90×3 40×2=350（元）；
5. 4艘大船的总花费360元大于3艘大船2艘小船的总花费350元，所以第二种方案更优；
6. 若继续枚举2艘大船、1艘大船、0艘大船，均不能找到更优方案[9][10]，因此确定“3艘大船2艘小船”为最优方案.

【总结】

1. 这类题目的本质是在多种约束条件下解非负整数不定方程mx ny=A，（m、n、A均为已知数）；
2. 一定要事先计算x和y的理论人均从而确定枚举x还是枚举y（不妨设x为枚举对象）；
3. 若x最大等于x0时已经有(x0,y0)满足不定方程，则(x0,y0)已是最优解；
4. 若上一条不满足，则继续从大到小枚举x，直到第一次出现(x1,y1)满足不定方程，此时(x1,y1)是最优解[11].

参考

1. ^其实就是中学的线性规划：设大船x只小船y只，满足：①x,y为整数②0≤x≤4③0≤y≤10④10x 4y≥38，使目标函数：90x 40y最小.
2. ^枚举法多适用于整数不定方程，如2x y=10，我们对x按从小到大的顺序依次枚举有以下非负整数解(x,y)：(1,8)(2,6)(3,4)(4,2)(5,0).
3. ^对大船数x枚举还是对小船数y枚举
4. ^从多到少枚举还是从少到多枚举
5. ^租整艘船的花费除以最多可坐人数.
6. ^假如全班40人，租大船90元坐10人，租小船40元坐4人，因为大船人均9元小于小船人均10元，所以选大船，又因为40人÷10人/艘=4艘，所以租4艘大船，并且每艘船都满员.
7. ^租整艘船的花费除以船上实际人数.
8. ^根据经验，题目至少有一种两类船都坐满的方案
9. ^设大船数为x，小船数为y，非负整数解(x,y)满足10x 4y=38时一定比满足10x 4y＞38更优，因为理论人均一定小于实际人均.
10. ^若非负整数解(x1,y1)与(x2,y2)都满足不定方程10x 4y=38，且x1＞x2，则(x1,y1)更优，因为大船理论人均小于小船理论人均，这也是为什么我们要从多到少去枚举大船数x，这样做保证了最少的枚举次数.
11. ^再次强调，由于是对x从大到小枚举，枚举到的x1一定比枚举到后面的某个x2大

【看到这的你已经是租船专家了，点赞升级为租船大师】,