例如,在给定面额集 1、2、5、10、20、50 的情况下,要获得 237 的值,构成该值的最佳方法是 4x50 + 1x20 + 1x10 + 1x5 + 1x2。但是如何在 PHP 中以编程方式实现呢?
问问题
289 次
1 回答
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);
在此示例中,您只有一个数量3
for 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”。
于 2013-08-29T14:40:20.757 回答