3

给定一个长度为 n 的数组 x 和一组数组 S，使得 S 中的每个数组的长度为 n，找到 S 中的数组 G 的最大大小集，使得对于所有 1 <= i <= n，x[i] >= sum(g[i]) 对于 G 中的所有 g。

例如，如果 x = [3, 3] 且 S = {[3, 0], [1, 1], [2, 1]}，则最佳集合是 {[1, 1], [2, 1]}因为总和是 [3, 2] 并且每个索引处的元素小于 x 中的对应元素。{[3, 0], [1, 1]} 不起作用，因为总和为 [4, 1]，并且 4 > x[0] = 3。

是否存在运行时间是 n 和 |S| 中多项式的算法？

背景/背景：这个问题来自一个关于拼字游戏的问题。给定一个瓦片列表和一个单词，你能用瓦片组成单词吗？我将它扩展到给定一个瓷砖列表和一个单词列表，列表中可以从瓷砖形成的最大单词数是多少？

4

1 回答 1

3

这是多维背包问题。

为了证明不存在算法，多项式时间n和|S|（或证明这是一个强 NP-hard 问题），简化这个问题，只允许1数组x和值0或1数组的值S。经过这种简化，我们得到了Set packing的优化版本，这是一个经典的 NP 完全问题。

与集装问题的关系表明也没有好的近似算法。

这使得算法的选择非常有限：

  1. 分支定界。
  2. 整数线性规划。
  3. 模拟退火或禁忌搜索等元启发式算法。
于 2012-10-17T22:14:12.183 回答