这是一个创建于 550 天前的主题，其中的信息可能已经有所发展或是发生改变。
需要给学生分配校车乘车路线
if __name__ == '__main__': #每路车剩下的空位 line_left_Num = { '5 路':6, '6 路':11, '9 路': 4, '10 路': 9, '11 路': 18, '12 路': 21, '17 路': 36, '18 路': 41, '21 路': 6, '60 路': 20 } # 每个站点还需要分配的学生人数 site_stu_num = { '江山里澜湾小区':21, '赞贤路小学、中航云府(赣康路)':30, '登峰大道中(城市家园)':7, '中海滨江壹号':13, '中海国际东郡 B 区(南康路)':30, '登峰大道南(中航公元)':64 } # 会经过该站点的线路 site_line = { '江山里澜湾小区': ['11 路','17 路'], '赞贤路小学、中航云府(赣康路)': ['5 路','9 路','12 路'], '登峰大道中(城市家园)': ['10 路','18 路'], '中海滨江壹号': ['6 路','21 路'], '中海国际东郡 B 区(南康路)': ['17 路','60 路'], '登峰大道南(中航公元)': ['11 路','17 路','18 路'] } 怎么设计一个算法给在不超载的情况下尽可能把学生都安排上，得到每个站点的每条线路分配人数，比如江山里澜湾小区，11 路分配 6 人，17 路分配 15 人，
 | 1 ivae OP 尝试用贪心算法和动态规划去算，没有太多的思路 |
 | 2 Sawyerhou 2024-06-15 17:51:26 +08:00 via Android 给每个学生编个号，然后随便初始化一下，尝试让每个已经上车学生换车，看能不能让其他没上车的学生上车，如果能，继续遍历，如果不能，直接输出？ |
 | 3 sillydaddy 2024-06-15 18:21:31 +08:00 这个是线性规划。假设所有的站点分别为 s0, s1, s2, s3...sn ，共有 m 路车分别为 b0, b1, b2...bm 。然后 N_s0_b0 来表示 b0 路车在站点 s0 分配的人数。 那么可以针对所有的 N_si_bi ，列出一组线性不等式。 首先是在 s0 这个站点，m 路车一共分配的人数要大于该站点等待上车的人数，即 N_s0_b0 + N_s1_b0 + N_s2_b0 + ... + N_s0_bm >= s0 站等待人数 然后是对于 b0 路车，所有 n 个站点上这辆车的人数小于该路车的空位，即 N_s0_b0 + N_s1_b0 + ... + N_sn_b0 <= b0 路车空位 把上面的不等式同样应用到所有的 n 个站点和 m 路车，就可以得到 n + m 个线性不等式。 线性规划就是解决这种问题的。可以搜一下现有的线性规划库。英文叫 Linear Programming 。 举几个我考察的例子： https://github.com/jvail/glpk.js GPL ，似乎适合大规模的求解，比如上万的变量和约束？ https://www.npmjs.com/package/lpsolver MIT ，最简洁，但只有标准形式 https://www.npmjs.com/package/lp_solve LGPL ，比较受欢迎，包大小比较大 2MB ，性能好，规范 https://www.npmjs.com/package/yalps MIT ，看起来很合适，性能也不错，上千的变量和约束只需要几十毫秒 https://www.npmjs.com/package/simple-simplex MIT ，看起来也不错，使用友好 https://github.com/IainNZ/SimplexJS js ，拿来就能用，但不规范 https://www.npmjs.com/package/@bygdle/Javascript-lp-solver 似乎的新增加的， 来自 https://github.com/JWally/jsLPSolver ，300 多个 star ，性能也不错。 |
| 4 sillydaddy 2024-06-15 18:24:53 +08:00 上面的有一个不等式列错了： 首先是在 s0 这个站点，m 路车一共分配的人数要大于该站点等待上车的人数，即 N_s0_b0 + N_s0_b1 + N_s0_b2 + ... + N_s0_bm >= s0 站等待人数 |
| 5 ivae OP @sillydaddy 谢谢，我试试 |
| 6 Sawyerhou 2024-06-16 08:19:50 +08:00 via Android 如果是算法题，不建议调包，会和面试官手里的答案对不上。如果是生产问题，那楼上说的对，组合优化的包很好用。 |
Select Language