Find the constituents of a specific number-CodePudding

I'm trying to figure out how I can find constituents of a specific number. Numbers can only be: array (700, 800, 900, 950, 1000, 1100, 1200, 1300).

For example, the given number is 3500. So, components could be 1200, 1200, 1100. If the number is not evenly divisible, then need find the nearest values with the minimum remainder.

Here's what I got:

<?php
$amount = 3000;

$sizes = array(1300, 1200, 1100, 1000, 950, 900, 800, 700);

$result = array();

foreach ($sizes as $size) {
    $result[$size] = floor($amount / $size);
    $amount -= $result[$size] * $size;
}

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

Output:

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

But 1300 * 2 = 2600, when it would be nice to use 1000 * 3.

Please help me optimize it for finding the closest values.

CodePudding user response：

Build a result array which contains the amount ('size') multiplied by 'times', and the 'remainder'. Then sort the result array by 'remainder', and if remainders are the same additionally by 'times':

$amount = 3000;
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ];

$result = [];

foreach ($sizes as $size) {
  $temp = (int)floor($amount / $size);
  $result[] = [
      'size' => $size,
      'times' => $temp,
      'remainder' => $amount - $temp * $size
  ];
}

usort($result, static function ($item1, $item2): int {
  $comparison = $item1['remainder'] <=> $item2['remainder'];
  return $comparison === 0 ? $item1['times'] <=> $item2['times'] : $comparison;
});

print_r($result);

This will print:

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

    [1] => Array
        (
            [size] => 950
            [times] => 3
            [remainder] => 150   // second best result
        )

    [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         // better than next
            [remainder] => 600   // same as next
        )

    [6] => Array
        (
            [size] => 800
            [times] => 3         // worse than previous
            [remainder] => 600   // same as previous
        )

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

CodePudding user response：

$amount = 3000;
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ];
$maxDepth = (int)( $amount / min($sizes) );

$result = [];
for ($depth = 1; $depth <= $maxDepth; $depth  ) {
  foreach (combinations($sizes, $depth) as $combination) {
    rsort($combination);
    $remainder = $amount - array_sum($combination);
    if ($remainder >= 0) {
      $result[] = [
          'remainder' => $remainder,
          'combination' => $combination
      ];
    }
  }
}

usort($result, static function ($item1, $item2): int {
  $comparison = $item1['remainder'] <=> $item2['remainder'];
  return $comparison === 0 ? count($item1['combination']) <=> count($item2['combination']) : $comparison;
});

print_r($result);

// The following code is from: 
// https://rosettacode.org/wiki/Combinations_with_repetitions#PHP

function combinations(array $arr, int $k): array {
  if ($k === 0) {
    return [ [] ];
  }
  if (count($arr) === 0) {
    return [];
  }
  $head = $arr[0];
  $combos = [];
  foreach (combinations($arr, $k - 1) as $subCombination) {
    array_unshift($subCombination, $head);
    $combos[] = $subCombination;
  }
  array_shift($arr);
  return array_merge($combos, combinations($arr, $k));
}

Result: