3

さまざまな数値 {5,6,1,67,13,9,14,15} の配列と、次のような要件のリストがあるとします: R1: set(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:配列にもあるセット (.......) から少なくとも k 個の数値を選択する必要があります。

したがって、問題は、指定された配列がすべての要件に一致するかどうかを判断するための多項式時間アルゴリズムを見つけることであり、配列の各数値は 1 つの要件のみを満たすためにのみ使用できます。

私の解決策は次のようになります：

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 となります。

私は間違っているかもしれませんが、これは Karp の NP 完全問題の 1 つである 0-1 整数計画法のように思えますね?

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

于 2012-10-25T22:40:49.180 に答える