高考题中的高等背景(14)——匈牙利算法【2024年新课标Ⅱ卷第14题】

文章预览

高考题中的高等背景(14)——匈牙利算法 2024年新课标Ⅱ卷第14题看似考查排列组合，其实还考查了整数规划问题中的一个经典算法——匈牙利算法． 因为个人水平有限，如果有误欢迎指出． 题目 Fiddie个人解答 依据乘法原理，选法一共有 种． 注意到，如果把某一行或某一列都加上同一个数，那么取到最大值的方格取法不变．(*) 所以，首先把第一列、第二列、第三列、第四列分别减去10、20、30、40，得到 然后再把上面方格表的第一行、第二行、第三行、第四行分别减去1、2、3、4，得到 记 为第 行取到的方格所在列数，则容易看出，当取到的四个方格为 ， ， ， 时（即第一行取第2个，第二行取第3个，第三行取第4个，第四行取第1个），如上方格表中选中方格的4个数字之和取到最大．回到原来的方格表，利用(*)，取到的数分别为21，33，43，15 ………………………………