斜素欣 发表于 2025-6-7 10:17:56

[高中数学&算法]浅谈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

丁若云 发表于 2025-11-13 06:10:13

谢谢分享，试用一下

丧血槌 发表于 2025-11-21 04:00:12

感谢发布原创作品，程序园因你更精彩

劳暄美 发表于 2025-11-28 04:57:50

感谢发布原创作品，程序园因你更精彩

疝镜泛 发表于 2025-11-28 18:29:16

过来提前占个楼

命煦砌 发表于 2025-12-11 17:25:36

谢谢分享，辛苦了

百杲憔 发表于 2025-12-11 18:04:57

前排留名，哈哈哈

杼氖 发表于 2025-12-15 09:46:00

用心讨论，共获提升！

祺簇 发表于 2025-12-15 16:42:50

谢谢楼主提供！

吉芷雁 发表于 2025-12-19 22:17:39

感谢分享，学习下。

颓哀 发表于 2025-12-21 03:35:34

感谢分享

廖彗云 发表于 2026-1-1 02:49:16

用心讨论，共获提升！

采序 发表于 2026-1-9 01:11:07

谢谢分享，辛苦了

广性 发表于 2026-1-19 00:04:34

收藏一下   不知道什么时候能用到

均浇 发表于 2026-1-21 21:57:54

这个有用。

琦谓 发表于 2026-1-22 06:34:31

谢谢分享，试用一下

乃阕饯 发表于 2026-1-23 05:23:16

东西不错很实用谢谢分享

梅克 发表于 2026-1-23 08:52:47

感谢发布原创作品，程序园因你更精彩

邹弘丽 发表于 2026-1-23 09:17:43

谢谢分享，试用一下

粹脍誊 发表于 2026-1-26 09:26:47

懂技术并乐意极积无私分享的人越来越少。珍惜
页: [1] 2
查看完整版本: [高中数学&算法]浅谈2024新高考II卷T14中的算法模型