○問題概要硬貨(10,50,100,500円玉)を複数持っています。m円分の買い物をしたときに現在所持している硬貨の枚数をできるだけ減らそうとします。
硬貨の枚数を最小にするときに買い物で支払う硬貨の枚数をそれぞれ求めましょう。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2007
○解説同じ種類の硬貨は最大でも20枚なのでO(n^4)の全探索で求めることが可能です。
と思っていましたが、PHPだと結構時間かかります。19secくらいかかりました。
PHPの割り算で割り切れない場合の値がdouble型になるのでint型にキャストするのを忘れないようにしましょう。
○提出したコード<?php
$coins = array(500, 100, 50, 10);
$flg = false;
while (fscanf(STDIN, "%d" , $cost) && $cost) {
$mycoins = explode(' ', trim(fgets(STDIN)));
if ($flg) print "\n";
$flg = true;
$a = $b = $c = $d = $min = 10000;
$cnt = 0;
foreach ($mycoins as $value) {
$cnt += $value;
}
for ($i = 0; $i <= $mycoins[0]; $i++) { // 10
for ($j = 0; $j <= $mycoins[1]; $j++) { // 50
for ($k = 0; $k <= $mycoins[2]; $k++) { // 100
for ($l = 0; $l <= $mycoins[3]; $l++) { // 500
$sum = $i * 10 + $j * 50 + $k * 100 + $l * 500;
if ($sum < $cost) continue;
$sum -= $cost;
$count = $cnt - $i - $j - $k - $l;
foreach ($coins as $value) {
$count += (int)($sum / $value);
$sum %= $value;
}
if ($count < $min) {
$min = $count;
$a = $i;
$b = $j;
$c = $k;
$d = $l;
}
}
}
}
}
if ($a) print "10 " . $a . "\n";
if ($b) print "50 " . $b . "\n";
if ($c) print "100 " . $c . "\n";
if ($d) print "500 " . $d . "\n";
}