選擇從一組x和y的k個項目，以滿足特定的標準

我已經給x和y項目，我需要選擇一些x有的y有一定的約束說x < 10和y < 5和總數應p。選擇從一組x和y的k個項目，以滿足特定的標準

如何解決這樣的問題。算法/數學技術。

2012-02-21 Avinash

總數應爲k或P的算法？ – sgowd 2012-02-21 07:02:47

我想這裏有一個更深層的語言問題。你有x個項目，還是從（0到x）的值，y是相同的？項目的數量或其值的總和是否必須是p？你需要總和爲p的對（x + y）還是每個組合（x1 + x2，... + xn + y1，+ y2 + ... + ym）= p？ – 2012-02-21 10:25:35

訣竅是，我們只需要經過一個陣列（例如在x_array），我們可以計算出Ÿ使用P-X = Y。現在我們只需要確保y在y_array中，並且我們知道我們有我們的答案。爲了確保y在y_array中，我們創建一個集合或二叉搜索樹來進行快速查找。

下面是一些Python代碼：

p=13 
xs=[1,3,99,9,18] 
ys=[10,4,33] 

y_set=set(ys) 

#y=p-x 
results=((x,p-x) for x in xs if x<10 and p-x<5 and p-x in y_set) 

print "x=%s,y=%s,p=13" % results.next() 
'x=9,y=4,p=13'

來源

2012-02-21 08:15:45

你試圖做這樣的事情：

void main(void) { 
    int x[] = {3, 5, 7, 10} 
    int y[] = {5, 9, 12, 23} 
    int i=0, j=0; 
     for(i=0; i<4; i++) 
     { 
     for(j=0; j<4; j++) 
     { 
      if (x[i]<10 && y[j]<5) 
      { 
       if(x[i]+y[j]==p) 
       { 
        //do something 
       } 
      } 
     } 
    } 
}

來源

2012-02-21 07:21:05 John

否y低於5. :)如果在迭代j之前測試x [i] <10，則可能爲大x和y節省大量時間。 – 2012-02-21 10:29:39

最快的算法，我知道會是：

讓m是最大的您約束和z項目由m限制。在你的情況下，m = 10, z = x。這是因爲隨着m增長，p-m減小。
我假設你的物品是通用的。創建地圖和關聯的關鍵p - z[i].value()到z[i]
取每個項目obj於其他列表中（在你的情況y），看看如果obj.value()是地圖的關鍵。如果是這樣，節省obj.value()和map[obj.value()]

使用檢索在固定時間O(1)地圖的財產，你有運行O(sizeof(x)+sizeof(y))

來源

2012-02-21 10:00:20 UmNyobe

選擇從一組x和y的k個項目，以滿足特定的標準

回答

相關問題