PHP实现从指定数组中查找目标数值的最小余数最优组成方案

你当前使用的是贪心取最大元素的算法，仅能得到局部最优解，无法保证全局余数最小，因此会出现目标值3000时得到余数400的非最优结果。

采用动态规划算法遍历所有可能的组合，可确保找到余数最小的全局最优解，代码实现如下：

<?php
function findOptimalCombination(int $target, array $sizes): array
{
    // 初始化dp数组，dp[i]存储凑出金额i的最优组合，key是元素值，value是数量
    $dp = array_fill(0, $target + 1, null);
    $dp[0] = []; // 金额0的组合为空

    foreach ($sizes as $size) {
        for ($i = $size; $i <= $target; $i++) {
            if ($dp[$i - $size] !== null) {
                $newCombination = $dp[$i - $size];
                $newCombination[$size] = ($newCombination[$size] ?? 0) + 1;
                // 相同金额下优先选择元素数量更少的组合
                if ($dp[$i] === null || count($newCombination) < count($dp[$i])) {
                    $dp[$i] = $newCombination;
                }
            }
        }
    }

    // 从目标值往下找第一个存在的组合，就是余数最小的解
    for ($i = $target; $i >= 0; $i--) {
        if ($dp[$i] !== null) {
            // 统一输出格式，未用到的size默认补0
            $result = array_fill_keys($sizes, 0);
            foreach ($dp[$i] as $size => $count) {
                $result[$size] = $count;
            }
            return [
                'combination' => $result,
                'total_amount' => $i,
                'remainder' => $target - $i
            ];
        }
    }
    return [];
}

// 测试调用
$target = 3000;
$sizes = [1300, 1200, 1100, 1000, 950, 900, 800, 700];
$result = findOptimalCombination($target, $sizes);

echo '<pre style="direction: ltr;">';
print_r($result);
echo '</pre>';
?>

目标值为3000时输出：

Array
(
    [combination] => Array
        (
            [1300] => 0
            [1200] => 0
            [1100] => 0
            [1000] => 3
            [950] => 0
            [900] => 0
            [800] => 0
            [700] => 0
        )
    [total_amount] => 3000
    [remainder] => 0
)

目标值为3500时输出：

Array
(
    [combination] => Array
        (
            [1300] => 0
            [1200] => 2
            [1100] => 1
            [1000] => 0
            [950] => 0
            [900] => 0
            [800] => 0
            [700] => 0
        )
    [total_amount] => 3500
    [remainder] => 0
)

内容的提问来源于stack exchange，提问作者Anton