謎題：如何按特定列的特定總和對行進行分組

Question

如何將以下行分成3組，其中「美元」的總和爲10.所有行必須使用且不得超過一次。

row|dollars 
1|1 
2|1 
3|1 
4|1 
5|1 
6|1 
7|3 
8|4 
9|7 
10|10 

一（許多可能的）期望的結果會是...

Row Group 1 = 10 
Row Group 2 = 7,9 
Row Group 3 = 1,2,3,4,5,6,8 

附加題： 時，它不是數學上可能各組得到的確切$ 10的總和，是有公式讓我們最接近那？

我雖然也許「有總和（元）= 10」，對於密切的解決方案，只是排序和分配一個行一組，但是這並沒有讓我接近。

Group Row By Sum of Specific Column equal to Specific Value對此有點觸動，但是，假設它們可能是數百萬行，則會出現性能問題。 我很難過。

如果有幫助，我使用php和mysql。一個純SQL解決方案將是理想的，但一些組合也會很好。感謝您的任何建議。

編輯：如果我不清楚，我想返回使這成爲可能的行，而不僅僅是「分組」。

Answer 1

我不認爲你可以只用SQL做到這一點，但它肯定可以幫幫忙。我開始有一個像select * from data where dollars <= 10 order by dollars desc這樣的查詢，然後在php中做一個算法，通過結果並添加了美元，直到它找到三個加起來爲10的組。直到找到正確的總和，然後存儲它，從列表中刪除這些項目並重新開始，三次。我正在使用我的電話，但當我到達我的電腦時，會以一個有效的例子更新答案。

編輯：到了我的電腦。這是非常混亂的代碼，但它應該引導你朝着正確的方向發展。

$dataset = [10,7,4,3,1,1,1,1,1,1]; 
$results = []; 

function add_to_ten(&$data) { 
    $sum = 0; 
    $results = []; 

    foreach ($data as $index => &$datum) { 
     if ($datum == 0) { 
      continue; 
     } 
     if ($sum + $datum <= 10) { 
      $sum += $datum; 
      $results[] = $index; 
      $datum = 0; 
     } 
     if ($sum == 10) { 
      return $results; 
     } 
    } 
} 

print_r(add_to_ten($dataset)); 
print_r(add_to_ten($dataset)); 
print_r(add_to_ten($dataset));