Q14 現地で使いやすい両替

PHPのソース

<?php
Solve(11254);
Solve(45678);

class ResultClass
{
    public $ToatlCoinCnt;
    public $EachCoinCntArr;
}

function Solve($pYen)
{
    $CoinCombiArr = DeriveCoinCombiArr();

    $ResultArr = array();
    foreach ($CoinCombiArr as $EachCoinCombi){
        $RestYen = $pYen - array_sum($EachCoinCombi);
        if ($RestYen < 0) continue;

        $CurrResult = new ResultClass();
        $CurrResult->ToatlCoinCnt = count($EachCoinCombi);
        $CurrResult->EachCoinCntArr = array();

        foreach($EachCoinCombi as $EachCoinVal){
            $CurrResult->EachCoinCntArr[$EachCoinVal] = 1;
            
            if($EachCoinVal <= $RestYen){
                $ModVal = $RestYen % $EachCoinVal;
                $SyouVal = ($RestYen - $ModVal) / $EachCoinVal;
                $CurrResult->EachCoinCntArr[$EachCoinVal] += $SyouVal;
                $CurrResult->ToatlCoinCnt += $SyouVal;
                $RestYen = $ModVal;
            }
        }
        if($RestYen == 0) $ResultArr[] = $CurrResult;
    }

    //使用した紙幣と硬貨の種類の最大値を求める
    $MaxCoinCount = 0;
    foreach($ResultArr as $EachResult){
        $CurrCnt = count($EachResult->EachCoinCntArr);
        if($MaxCoinCount < $CurrCnt)
            $MaxCoinCount = $CurrCnt;
    }

    //使用した紙幣と硬貨の種類が最大値での、
    //全体の枚数の最小値を求める
    $MinToatlCoinCnt = PHP_INT_MAX;
    foreach($ResultArr as $EachResult){
        if(count($EachResult->EachCoinCntArr) < $MaxCoinCount)
            continue;
        if($EachResult->ToatlCoinCnt < $MinToatlCoinCnt)
            $MinToatlCoinCnt = $EachResult->ToatlCoinCnt;
    }

    foreach($ResultArr as $EachResult){
        if(count($EachResult->EachCoinCntArr) < $MaxCoinCount)
            continue;
        if($EachResult->ToatlCoinCnt < $MinToatlCoinCnt)
            continue;

        printf('金額が%d円での、最小枚数は%d枚で、内訳は' , $pYen , $MinToatlCoinCnt);
        var_export($EachResult->EachCoinCntArr);
        echo PHP_EOL;
    }
}

class JyoutaiDef
{
    public $CurrInd;
    public $CurrArr;
}

//紙幣と硬貨の組合せの配列を返す
function DeriveCoinCombiArr()
{
    $CoinArr = array(1,5,10,50,100,500,1000,2000,5000,10000);
    $UB = count($CoinArr)-1;

    $WillReturn = array();

    $Stk = new SplStack();
    $WillPush = new JyoutaiDef();
    $WillPush->CurrInd = 0;
    $WillPush->CurrArr = array();
    $Stk->push($WillPush);

    while($Stk->isEmpty() == false){
        $Popped = $Stk->pop();

        for($I = $Popped->CurrInd ; $I <= $UB ; $I++){
            $WillPush = clone $Popped;
            $WillPush->CurrInd = $I+1;
            $WillPush->CurrArr[] = $CoinArr[$I];
            $Stk->push($WillPush);
            $WillAdd = $WillPush->CurrArr;
            rsort($WillAdd);
            $WillReturn[] = $WillAdd;
        }
    }
    return $WillReturn;
}

実行結果

金額が11254円での、最小枚数は19枚で、内訳はarray (
  5000 => 1,
  2000 => 2,
  1000 => 1,
  500 => 2,
  100 => 1,
  50 => 2,
  10 => 4,
  5 => 2,
  1 => 4,
)
金額が45678円での、最小枚数は17枚で、内訳はarray (
  10000 => 3,
  5000 => 2,
  2000 => 2,
  1000 => 1,
  500 => 1,
  100 => 1,
  50 => 1,
  10 => 2,
  5 => 1,
  1 => 3,
)

解説

深さ優先探索で、組合せを列挙し、
貪欲法を使ってます。