找回密码
 立即注册
首页 业界区 科技 [高中数学&算法]浅谈2024新高考II卷T14中的算法模型 ...

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

斜素欣 2025-6-7 10:17:56
原题回顾:在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
您需要登录后才可以回帖 登录 | 立即注册