胡乱想到的东西求解
  • 板块学术版
  • 楼主P2441MPM2.4
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/2/2 20:43
  • 上次更新2025/2/3 11:20:58
查看原帖
胡乱想到的东西求解
1063026
P2441MPM2.4楼主2025/2/2 20:43

nn 个物品,还有 mm 条限制,第 ii 条形如 SiS_i 中的物品必须被划分到 AA 中,且 TiT_i 中的物品必须被划分到 BB 中。试将 nn 个物品划分成两个不交的集合 AABB,最大化满足的限制数。

不保证 SiTi=US_i\cup T_i=U,其中 UU 表示 nn 个物品构成的集合。

想知道有没有多项式时间复杂度的做法。

2025/2/2 20:43
加载中...