PHP中优化数字构成查找：最小余数与最优单类型组合算法

<?php
$amount = 3000;
$sizes = array(1300, 1200, 1100, 1000, 950, 900, 800, 700); // 建议降序排列以符合贪婪策略

$result = array();
$remainingAmount = $amount; // 使用一个变量来跟踪剩余量

foreach ($sizes as $size) {
    if ($remainingAmount >= $size) {
        $times = floor($remainingAmount / $size);
        $result[$size] = $times;
        $remainingAmount -= $times * $size;
    } else {
        $result[$size] = 0;
    }
}

echo '<pre>'; print_r($result); echo '</pre>';
?>

Array
(
    [1300] => 2
    [1200] => 0
    [1100] => 0
    [1000] => 0
    [950] => 0
    [900] => 0
    [800] => 0
    [700] => 0
)

<?php
$amount = 3000;
// 构成数数组，顺序不影响最终结果，因为是独立计算
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ];

$results = []; // 注意：这里改名为 $results 以避免与 $result 混淆

foreach ($sizes as $size) {
  $times = (int)floor($amount / $size); // 计算当前构成数能使用的最大次数
  $remainder = $amount - $times * $size; // 计算此时的剩余量

  $results[] = [
      'size' => $size,
      'times' => $times,
      'remainder' => $remainder
  ];
}

// 使用 usort 进行自定义排序
usort($results, static function ($item1, $item2): int {
  // 首先按 'remainder' 升序排序
  $comparison = $item1['remainder'] <=> $item2['remainder'];

  // 如果 'remainder' 相同，则按 'times' 升序排序
  // 这样在余数相同的情况下，会优先选择使用次数较少的方案
  return $comparison === 0 ? $item1['times'] <=> $item2['times'] : $comparison;
});

echo '<pre>'; print_r($results); echo '</pre>';
?>

Array
(
    [0] => Array
        (
            [size] => 1000
            [times] => 3
            [remainder] => 0
        )

    [1] => Array
        (
            [size] => 950
            [times] => 3
            [remainder] => 150
        )

    [2] => Array
        (
            [size] => 700
            [times] => 4
            [remainder] => 200
        )

    [3] => Array
        (
            [size] => 900
            [times] => 3
            [remainder] => 300
        )

    [4] => Array
        (
            [size] => 1300
            [times] => 2
            [remainder] => 400
        )

    [5] => Array
        (
            [size] => 1200
            [times] => 2
            [remainder] => 600
        )

    [6] => Array
        (
            [size] => 800
            [times] => 3
            [remainder] => 600
        )

    [7] => Array
        (
            [size] => 1100
            [times] => 2
            [remainder] => 800
        )
)