30单位上限下达成指定战力的最低成本舰队配置算法求解

问题本质 #

这是带双约束的最小成本组合优化问题，约束条件为：

• 选中单位总数量 ≤ 30
• 选中单位总战力 ≥ 目标值x
• 优化目标：选中单位总价格最低

第一步：数据预处理（必做，直接把计算量压到原来的1%以下） #

可选单位共3万个，但单单位战力取值范围只有1~200，因此先按战力值分组，每个战力分组下仅保留价格最低的1个单位，剩余高价同战力单位直接淘汰。
这一步时间复杂度仅O(n)，处理后可选单位最多仅200个，完全解决原始数据量过大的问题。

第二步：核心动态规划求解 #

因为单位数上限仅30，单单位最高战力200，因此战力上限最高为30*200=6000，如果你的目标战力x超过6000时可直接返回无解。

状态定义 #

定义二维数组 dp[k][p] 为：恰好选中k个单位时，达到总战力p所需的最小成本。为了进一步压缩空间，所有超过x的战力统一按x存储，战力维度最大仅为x，无需存储更高战力的数值。

初始化 #

将dp[0][0] = 0，其余所有状态初始化为无穷大（可以用一个远大于可能最高总成本的数值代替，比如1e9）。

状态转移 #

遍历每个预处理后的单位（战力s，成本c）：

• 倒序遍历单位数k从29到0（避免重复选择同一个单位）
• 倒序遍历当前总战力p从当前最大值到0
• 如果dp[k][p]不为无穷大，则更新状态：
  dp[k+1][min(p+s, x)] = min(dp[k+1][min(p+s, x)], dp[k][p] + c)

结果计算 #

遍历k从1到30，取dp[k][x]的最小值即为满足约束的最低成本。如果需要输出具体的单位组合，可以额外维护一个prev转移数组，记录每个状态的转移来源，最后倒推即可得到具体配置。

时间复杂度分析 #

总计算量为 200（预处理后单位数） * 30（最大单位数） * 6000（最大战力） = 3.6e7，即便是低端移动设备也能毫秒级跑完，完全不会出现计算卡顿的问题。

为什么比贪心PpP方案效果好 #

贪心仅按单位战力性价比排序的方案没有兼顾数量约束的影响，而该动态规划方案会遍历所有满足单位数约束的合法组合，完全覆盖你提到的高低战力混合性价比更高的场景，保证得到全局最优解。

内容的提问来源于stack exchange，提问作者Alex Pryor