我有部分長度的陣列，比賽爲示例起見： -計算最接近從數組值組合
array(150, 180, 270);
我然後有一個測量($a = 440)
我需要計算兩個最接近可能長度的組合大於$a，而無需手動編寫數百種可能的組合以便解決問題。
所以：
150
180
270
150 + 150
150 + 180
150 + 270
180 + 180
180 + 270
270 + 270
150 + 150 + 150
150 + 150 + 180
..和等。
這將需要爲次一組數字跑，而不僅僅是找到前兩場比賽和停止，爲150 + 150 + 150將是一個更接近比賽到$a比270 + 270，但可能之後運行。
編輯：我還需要存儲組成匹配的部分的組合，最好是在一個數組中。
我希望我已經解釋了這一點，以便有人能夠理解。
由於這是一個相當資源重腳本，我認爲提供選項以預先生成選項是一個好主意，然後使用該數據創建一個變量/對象/ sql腳本來永久存儲數據。舉例來說，做這樣的事情
SELECT * FROM combination_total WHERE size > YOUR_SIZE ORDER BY size ASC LIMIT 2;
新腳本我有類似，但它只是產生所有的組合，沒有任何重複的數組。看起來很快。請注意$ maxLength變量，該變量當前設置爲2000，可以使用您自己的最大可能大小進行修改。
<?php
$partLengths = array(150, 180, 270);
$currentCombinations = array(
array(
'total' => 150,
'combination' => array(150)
),
array(
'total' => 180,
'combination' => array(180)
),
array(
'total' => 270,
'combination' => array(270)
)
);
$maxLength = 2000;
$largestSize = 0;
function generateCombination() {
global $currentCombinations, $largestSize, $partLengths;
$tmpCombinations = $currentCombinations;
foreach ($tmpCombinations as $combination) {
foreach ($partLengths as $partLength) {
$newCombination = $combination['combination'];
$newCombination[] = $partLength;
sort($newCombination);
$newCombinationTotal = array_sum($newCombination);
if (!combinationExists($newCombination)) {
$currentCombinations[] = array(
'total' => $newCombinationTotal,
'combination' => $newCombination
);
}
$largestSize = ($newCombinationTotal > $largestSize) ? $newCombinationTotal : $largestSize;
}
}
}
function combinationExists($combination) {
global $currentCombinations;
foreach ($currentCombinations as $currentCombination) {
if ($combination == $currentCombination['combination']) {
return true;
}
}
return false;
}
while ($largestSize < $maxLength) {
generateCombination();
}
// here you can use $currentCombinations to generate sql/object/etc
var_dump($currentCombinations);
?>
下面的代碼是蠻力的，只測試2個值的可能組合，所以我知道它不完整。但是，這是一個開始。
更新：請參閱我的下面的其他答案，以獲得更好的解決方案，該解決方案適用於任何可能的組合，而不僅僅是2，並且已經過優化。
<?php
echo "<html><head><title>Test Array Sums</title></head><body>";
$testarray = array(2, 5, 9, 78, 332);
$target_value = 10;
$closest1 = 0;
$closest2 = 0;
$closest_sum = 0;
$closest_difference = 0;
$first_time_in_loop = TRUE;
foreach ($testarray AS $entry1)
{
foreach ($testarray AS $entry2)
{
if ($first_time_in_loop)
{
$first_time_in_loop = FALSE;
$closest1 = $entry1;
$closest2 = $entry2;
$closest_sum = $closest1 + $closest2;
$closest_difference = abs($target_value - $closest_sum);
}
$test_sum = $entry1 + $entry2;
if (abs($test_sum - $target_value) < $closest_difference)
{
if ($test_sum - $target_value >= 0)
{
// Definitely the best so far
$closest1 = $entry1;
$closest2 = $entry2;
$closest_sum = $closest1 + $closest2;
$closest_difference = abs($closest_sum - $target_value);
}
else if ($closest_sum - $target_value < 0)
{
// The sum isn't big enough, but neither was the previous best option
// and at least this is closer
$closest1 = $entry1;
$closest2 = $entry2;
$closest_sum = $closest1 + $closest2;
$closest_difference = abs($closest_sum - $target_value);
}
}
else
{
if ($closest_sum - $target_value < 0 && $test_sum - $target_value >= 0)
{
// $test_value is farther away from the target than the previous best option,
// but at least it's bigger than the target value (the previous best option wasn't)
$closest1 = $entry1;
$closest2 = $entry2;
$closest_sum = $closest1 + $closest2;
$closest_difference = abs($closest_sum - $target_value);
}
}
}
}
echo "Best pair: " . $closest1 . ", " . $closest2 . "<br />";
echo "</body></html>";
?>
能否限制測試值3的總數 - 或一些較大的數字 - 或者你真的需要把它擴大到所有可能的組合（即，如果4 + 4 + 5 + 4 + 4 + 5 + 3 + 5 + 4 + 5 + 3 + 4比26 + 26更接近你需要找到它嗎？）
如果你可以限制被測試的數字，比如5，那麼你可以擴展上面的循環以處理多達5個選擇。否則，需要編寫更復雜的循環。
此代碼計算出$ a之上最接近的組合，以及之後最接近的組合。它刪除重複項以加快速度。這不是超級優化，但最初的測試顯示它不是太糟糕，取決於$ a的初始值不是很大。
<?php
/* value in cm */
$a = 1020;
$partLengths = array(150, 180, 270);
$closestValue = array();
$secondClosest = array();
$currentCombinations = array(
array(
'total' => 150,
'combination' => array(150)
),
array(
'total' => 180,
'combination' => array(180)
),
array(
'total' => 270,
'combination' => array(270)
)
);
function getCombinations(&$currentCombinations, $partLengths,$a, &$closestValue, &$secondClosest) {
$tmpCombinations = $currentCombinations;
static $secondMatch = true;
for ($x=0;$x<count($partLengths);$x++) {
for ($y=0;$y<count($tmpCombinations);$y++) {
$newCombination = $tmpCombinations[$y]['combination'];
$newCombination[] = $partLengths[$x];
$newCombinationTotal = array_sum($newCombination);
sort($newCombination);
if (!combinationExists($currentCombinations, $newCombination, $newCombinationTotal)) {
$currentCombinations[] = array('total' => $newCombinationTotal, 'combination' => $newCombination);
}
if ($closestValue['total'] < $a) {
$oldGap = $a - $closestValue['total'];
$newGap = $a - $newCombinationTotal;
$newGap = ($newGap < 0) ? 0 - $newGap : $newGap;
if ($newGap < $oldGap) {
$secondClosest = $closestValue;
$closestValue['total'] = $newCombinationTotal;
$closestValue['combination'] = $newCombination;
}
} else {
$oldGap = $a - $secondClosest['total'];
$newGap = $a - $newCombinationTotal;
$oldGap = ($oldGap < 0) ? 0 - $oldGap : $oldGap;
$newGap = ($newGap < 0) ? 0 - $newGap : $newGap;
if ($newCombinationTotal > $a && $newCombinationTotal > $closestValue['total']) {
if ($secondMatch || $newGap < $oldGap) {
$secondMatch = false;
$secondClosest['total'] = $newCombinationTotal;
$secondClosest['combination'] = $newCombination;
}
}
}
}
}
}
function combinationExists(&$currentCombinations, $newCombination, $newCombinationTotal) {
foreach ($currentCombinations as $currentCombination) {
if ($currentCombination['total'] != $newCombinationTotal && $currentCombination['combination'] != $newCombination) {
return false;
}
}
return false;
}
while ($secondClosest['total'] <= $a) {
getCombinations($currentCombinations, $partLengths, $a, $closestValue, $secondClosest);
}
var_dump($closestValue);
var_dump($secondClosest);
?>
進一步建議，如果速度不成爲一個問題，就是預先生成所有組合，並將它們保存在某種散列/數據庫/等等，你可以很容易地訪問。
改進我以前的答案，這裏是一個版本，可用於測試任意數量的條目，達到最大數量。
UPDATE：（優化增加;見下文評論）
例如，如果所需的值是15，而列表是(1, 17, 20)，最好的選擇是1+1+1+1+1+1+1+1+1+1+1+1+1+1+1，所以你就必須讓$max_loops，至少爲15爲了找到這個匹配 - 即使列表中只有3個值！ (1, 133, 138)的情況更糟糕，其中期望的值是例如130。在這種情況下，您需要遞歸！你可以看到這可能是一個優化的噩夢。但是，下面的算法是有效的，並且相當優化。
<?php
echo "<html><head><title>Test Array Sums</title></head><body>";
$testarray = array(1, 3, 6);
$target_value = 10;
$current_closest_sum = 0;
$current_closest_difference = 0;
$first_time_in_loop = TRUE;
$max_loops = 10;
$current_loop = 0;
$best_set = array();
$current_set = array();
$sums_already_evaluated = array();
function nestedLoop($current_test = 0)
{
global $testarray, $target_value, $current_closest_sum, $current_closest_difference, $first_time_in_loop, $max_loops, $current_loop, $best_set, $current_set, $sums_already_evaluated;
++$current_loop;
foreach ($testarray AS $entry)
{
$current_set_temp = $current_set;
$current_set[] = $entry;
if ($first_time_in_loop)
{
$first_time_in_loop = FALSE;
$current_closest_sum = $entry + $current_test;
$current_closest_difference = abs($target_value - $current_closest_sum);
$best_set[] = $entry;
}
$test_sum = $entry + $current_test;
if (in_array($test_sum, $sums_already_evaluated))
{
// no need to test a sum that has already been tested
$current_set = $current_set_temp;
continue;
}
$sums_already_evaluated[] = $test_sum;
if ($test_sum > $target_value && $current_closest_sum > $target_value && $test_sum >= $current_closest_sum)
{
// No need to evaluate a sum that is certainly worse even by itself
$current_set = $current_set_temp;
continue;
}
$set_best = FALSE;
if (abs($test_sum - $target_value) < $current_closest_difference)
{
if ($test_sum - $target_value >= 0)
{
// Definitely the best so far
$set_best = TRUE;
}
else if ($current_closest_sum - $target_value < 0)
{
// The sum isn't big enough, but neither was the previous best option
// and at least this is closer
$set_best = TRUE;
}
}
else
{
if ($current_closest_sum - $target_value < 0 && $test_sum - $target_value >= 0)
{
// $test_value is farther away from the target than the previous best option,
// but at least it's bigger than the target value (the previous best option wasn't)
$set_best = TRUE;
}
}
if ($set_best)
{
$current_closest_sum = $test_sum;
$current_closest_difference = abs($current_closest_sum - $target_value);
$best_set = $current_set;
}
if ($current_loop < $max_loops)
{
if ($test_sum - $target_value < 0)
{
nestedLoop($test_sum);
}
}
$current_set = $current_set_temp;
}
--$current_loop;
}
// make array unique
$testarray = array_unique($testarray);
rsort($testarray, SORT_NUMERIC);
// Enter the recursion
nestedLoop();
echo "Best set: ";
foreach ($best_set AS $best_set_entry)
{
echo $best_set_entry . " ";
}
echo "<br />";
echo "</body></html>";
?>
更新：我已經添加了兩個小的優化，似乎有很大的幫助，並避免內存過載或哈希表查找。它們是：
（1）跟蹤所有先前評估的總和，並且不要再評估它們。 （2）如果總和（本身）已經比先前的測試更差，則跳過任何進一步的測試。
我認爲，通過這兩種優化，該算法在您的情況下可能適用於實際應用。
以前的評論下面，現在有些IRRELEVANT
我先前的評論，下面，有些沒有實際意義，因爲上面的兩個優化，似乎工作得很好。但是，無論如何我都會收到評論。
不幸的是，如上所述，上述循環是高度非優化的。必須通過避免重複測試（以及其他優化）來對其進行優化，以便在實際情況下工作。但是，它演示了一種可行的算法。
請注意，這是一個複雜的數學領域。各種優化可能有助於一種情況，但不是另一種。因此，要使上述算法高效工作，您需要討論實際的使用場景 - 部件列表中最大長度是否會有限制？什麼是長度範圍？另外，零件清單&的其他更細微的特徵儘管很微妙，但它們可能會在如何優化算法方面發生重大變化。
這是一個「理論」問題不足以產生所需解決方案的情況，因爲優化非常重要。因此，提出優化建議並不是特別有用。例如，倫納德的優化（通過保存先前測試過的所有組合）避免了重複，但對於較小的集合來說效果很好，但是對於較大的集合，內存使用率會爆炸（正如他指出的那樣）。這不是一個簡單的問題。
（代碼編輯〜2個小時後，以處理可能錯過組合由於限制遞歸到一定數量的遞歸 - 通過排序從高至低的陣列，最初）
還要注意，上面的代碼只保存一個組合。如果有兩種組合可以選擇最佳選擇，那麼上面的代碼可以相當簡單地進行修改，以將其全部保存起來。 – 2012-03-29 17:48:20
數組的大小是多少？ – safarov 2012-03-29 12:05:28
數組的大小與示例3中的大小相同。但是，這可能會有所不同： – billyonecan 2012-03-29 12:10:19
您是否正在尋找避免通過數組進行不必要迭代的* efficient *函數，或者您是否在尋找* any *函數（即使它非常非優化），因爲數組可能很小（小我的意思是，說100或更少）？後者非常簡單，我可以用一些示例代碼來回答;後者也可以完成，但有點複雜。 – 2012-03-29 12:36:12