php - 计算获得给定面额集合值的最佳方法

Question

例如，在给定面额集 1、2、5、10、20、50 的情况下，要获得 237 的值，构成该值的最佳方法是 4x50 + 1x20 + 1x10 + 1x5 + 1x2。但是如何在 PHP 中以编程方式实现呢？

Answer 1

你可以做这样的事情：

$number = 237;

$values = array(1, 2, 5, 10, 20, 50);
arsort($values); // greater to lower sorting
$numberOf = array();

foreach ($values as $v) {
    $numberOf[$v] = floor($number / $v);
    $number -= $numberOf[$v] * $v;
}

var_dump($numberOf);

这将产生：

array(6) {
  [50]=>
  int(4)
  [20]=>
  int(1)
  [10]=>
  int(1)
  [5]=>
  int(1)
  [2]=>
  int(1)
  [1]=>
  int(0)
}

演示

编辑：金额有限的面额

如果你没有无限面额，你可以试试这个：

$number = 237;

$values = array(1, 2, 5, 10, 20, 50);
$quantities = array(7, 1, 3, 5, 2, 3);
// sort by greater value to lower value
// but keeping the related quantities
array_multisort($values, SORT_DESC, $quantities);

$numberOf = array();

foreach ($values as $i => $v) {
    $quantity = $quantities[$i]; // get the corresponding quantity
    // if we have less than the required value, we put the max we can
    $numberOf[$v] = floor($number / $v) > $quantity ? $quantity : floor($number / $v);
    $number -= $numberOf[$v] * $v;
}

var_dump($numberOf);

在此示例中，您只有一个数量3for 50。因此，您将获得如下输出：

array(6) {
  [50]=>
  int(3)
  [20]=>
  int(2)
  [10]=>
  float(4)
  [5]=>
  float(1)
  [2]=>
  float(1)
  [1]=>
  float(0)
}

3 * 50 + 2 * 20 + 4 * 10 + 5 * 1 + 2 * 1 + 1 * 0 = 237

伊皮！
演示

另请参阅array_multisort()以了解此关键行：

array_multisort($values, SORT_DESC, $quantities);

更好的是，一个准备就绪的功能：

function getDenominations($amount, $denominations, $quantities = null) {
    if (is_array($quantities) && count($denominations) != count($quantities)) return false;
    array_multisort($denominations, SORT_DESC, $quantities);

    $numberOf = array();

    foreach ($denominations as $i => $v) {
        $quantity = $quantities[$i]; 
        $numberOf[$v] = floor($amount/ $v) > $quantity ? $quantity : floor($amount / $v);
        $amount -= $numberOf[$v] * $v;
    }

    return $amount == 0 ? $numberOf : false;
}

像这样使用：

$result = getDenominations(
    237,
    array(1, 2, 5, 10, 20, 50),
    array(7, 1, 3, 5, 0, 4)
);

var_dump($result);

返回值：数组|布尔

如果未指定数量，则返回无限数量的面额。如果指定，则数量有限。
如果数量不足或数组大小不同，则返回“false”。