3

假设您有一个不同数字的数组 {5,6,1,67,13,9,14,15}，以及这样的要求列表： R1：您必须从集合中选择至少 2 个数字（5,6， 10) 在这种情况下，它们也在你的数组中，它将是 5,6

R2：您必须从 set(9,13,67,5) 中选择至少 3 个数字，这些数字也在您的数组中。在这种情况下，它将是 9,13,67。请注意，我们不能选择 5，因为它已在 R1 中使用过

R3：您必须从 set(1,14,15,6) 中选择至少 2 个数字，这些数字也在您的数组中。在这种情况下，它可以是 1,14 或 1,15 或 14,15，我们将有多个满意。......

......

Rk：您必须从 set (.......) 中选择至少 k 个数字，这些数字也在您的数组中。

所以问题是找到一种多项式时间算法来确定给定数组是否满足所有要求，并且数组的每个数字只能用于满足一个要求。

我的解决方案是这样的：

determine(array a,R[]) //R[] is a array of requirements, array a is our checking array
{
     if R is empty return true   //we satisfied all the requirments
     if R[0] cannot be satisfied by our array a return false
     for each satisfactions
     {
       new array b=a-selected numbers for this satisfaction
       new rule array newR=R-R[0]    //remove the first rule of the rule array
       if determine(b,newR) is false     //we begin our recursive call
           we continue our loop since this means the current way of satisfaction does not work
       else return true
      }
         return false   //this means we finish checking all the satisfactions and cannot find a match we need to tell the last recursive call that this way does not work    
}

显然我的解决方案需要指数时间，任何人都可以提出多项式解决方案吗？

4

1 回答 1

1

在满足所有要求后，您将选择数组中的每个元素 (c(0), c(1), c(2), ... , c(n)) 次。

其中 c(i) 为 0 或 1。例如，您的约束告诉您 c(i) + c(j) + c(k) = 2。

我可能错了，但这似乎是 0-1 整数规划，这是卡普的 NP 完全问题之一，不是吗？

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

于 2012-10-25T22:40:49.180 回答