[高中数学&算法]浅谈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存储。
确定状态：
定义dp为当选取第i列，已选择的方案状压值为j时的最大值（不是所有有序对(i,j)都具有意义）。
至于状压值是什么：选取第一列那么状压值+2，选取第二列状压值+4，选取第三列状压值+8，选取第四列状压值+16；例如，状压值是18那么18=16+2，此时i=2，已选择的列数是第一列和第四列。
不难证明，对于任意一个状压值，由此计算出的选择的列的方案唯一。
初状态：
a的所有数字都移入dp[1
页:
[1]