[高中数学&算法]浅谈2024新高考II卷T14中的算法模型

原题回顾：在4x4方格表中选四个方格，要求每行每列恰有一个方格被选中，问四个数字之和的最大值。
|  11  |  21  |  31  |  40  |
|  12  |  22  |  33  |  42  |
|  13  |  22  |  33  |  43  |
|  15  |  24  |  34  |  44  |

Solution 1 暴力枚举

时间复杂度：O(n!)

枚举法在这里不过多提及，应该是考场上部分人的复杂且有效的方式解题。本文重点在下面。
Solution 2 状压DP

时间复杂度：O(n²2ⁿ）

该表格用a[j]存储。
确定状态：

定义dp[j]为当选取第i列，已选择的方案状压值为j时的最大值（不是所有有序对(i,j)都具有意义）。
至于状压值是什么：选取第一列那么状压值+2，选取第二列状压值+4，选取第三列状压值+8，选取第四列状压值+16；例如，状压值是18那么18=16+2，此时i=2，已选择的列数是第一列和第四列。
不难证明，对于任意一个状压值，由此计算出的选择的列的方案唯一。
初状态：


a[1][k]的所有数字都移入dp[1][1