コインを減らす払い方 DouKaku?

コインを減らす払い方

いま、あなたの財布の中にはコインがたくさん入っています。これを少しでも減らしたいと思います。

支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。

例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。Pythonで表現するならば下のような挙動をする関数を作ってください。

>>> pay(147, {1: 2, 10: 4, 100: 3})
{1: 2, 100: 2}

2007-07-01追記：　　minkeさんの指摘通り、「手元にある全てのコインを渡せば、結果としてもっとも枚数が少なくなる」ので、「渡した硬貨がおつりで返ってくるような渡し方は禁止」と条件を追加します。

post comment

Posted feedbacks - Nested

Flatten Hidden

結局のところ、手元にある全てのコインを渡せば、結果としてもっとも枚数が少なくなるように返ってくるわけですよね。

class Wallet
  def initialize(h)
    h.default = 0
    @@coins = [500, 100, 50, 10, 5, 1]
    @cont = Hash.new
    @@coins.each do |i|
      @cont[i] = h[i]
    end
  end
  def total
    sum = 0
    @cont.each do |k,v|
      sum += k * v
    end
    sum
  end
  def calc(n)
    h = Hash.new
    @@coins.each do |c|
      h[c] = n / c
      n %= c
    end
    h
  end
  def diff(after)
    ret = Hash.new
    @@coins.each do |c|
      if @cont[c] > after[c]
        ret[c] = @cont[c] - after[c]
      end
    end
    ret
  end
  def pay(expense)
    raise if total < expense
    after = calc(total - expense)
    ret = diff(after)
    @cont = after
    ret
  end
end

p Wallet.new({1=>2, 10=>4, 100=>3}).pay(147)

>結局のところ、手元にある全てのコインを渡せば、
>結果としてもっとも枚数が少なくなるように返ってくるわけですよね。

orz。その通りです。
「渡した硬貨がおつりで返ってくるような渡し方は禁止」と追記しておきます。
ご指摘ありがとうございます。

Scheme (Gauche) で。
愚直に、総当たりで調べるコードです。
実行例：

gosh> (pay 147 '((1 2) (10 4) (100 3)))
((1 2) (100 2))

(use srfi-1)
(use util.combinations)

(define *coins* '(500 100 50 10 5 1))

(define (changes due)
  (define (rec r c)
    (cond ((zero? r) '())
          ((<= (car c) r) (cons (car c) (rec (- r (car c)) c)))
          (else (rec r (cdr c)))))
  (rec due *coins*))

(define (score coins price)
  (let ((ch (changes (- (apply + coins) price))))
    (and (null? (lset-intersection = coins ch))
         (- (length coins) (length ch)))))

;; ((1 2) (10 4) (100 3)) => (1 1 10 10 10 10 100 100 100) etc.
(define (expand coin-list)
  (append-map (lambda (p) (make-list (cadr p) (car p))) coin-list))

;; (1 1 10 10 10 10 100 100 100) => ((1 2) (10 4) (100 3)) etc.
(define (condense coins)
  (map (lambda (g) (list (car g) (length g))) (group-collection coins)))

(define (pay price coin-list)
  (condense
   (values-ref (fold2 (lambda (payment max-score answer)
                        (or (and-let* (( (>= (apply + payment) price) )
                                       (s (score payment price))
                                       ( (> s max-score) ))
                              (values s payment))
                            (values max-score answer)))
                      #i-1/0 '()
                      (power-set* (expand coin-list)))
               1)))

総当たり、効率悪し。

import Data.Maybe
import Data.List

coins :: [Int]
coins = [500, 100, 50, 10, 5, 1]

numToCoins :: Int -> [Int]
numToCoins 0 = []
numToCoins n = let coin = whichCoinToUse n
               in
                 coin : numToCoins (n - coin)
    where
      whichCoinToUse :: Int -> Int
      whichCoinToUse n = fromJust $ find (<= n) coins

expand :: [(Int, Int)] -> [Int]
expand []                   = []
expand ((coin, quant) : xs) = replicate quant coin ++ expand xs

collapse :: [Int] -> [(Int, Int)]
collapse coins = [(head grp, length grp) | grp <- group $ sort coins]

score :: Int -> [Int] -> Maybe Int
score total coinsToUse
    | total > sum coinsToUse  -- お金が足りない
        = Nothing
    | otherwise               -- 減った枚数を返す
        = let changes = numToCoins $ abs $ total - sum coinsToUse
          in 
            Just $ length coinsToUse - length changes

powerSet :: [a] -> [[a]]
powerSet []     = [[]]
powerSet (x:xs) = let xss = powerSet xs
                  in
                    map (x:) xss ++ xss

pay :: Int -> [(Int, Int)] -> [(Int, Int)]
pay total wallet
    = let challenges = powerSet $ expand wallet
          possibles  = catMaybes $ map bindScore challenges
          bestWay    = last $ sortBy cmp possibles
      in
        collapse $ snd bestWay
    where
      bindScore :: [Int] -> Maybe (Int, [Int])
      bindScore challenge
          = do s <- score total challenge
               return (s, challenge)

      cmp :: (Int, [Int]) -> (Int, [Int]) -> Ordering
      cmp (a, as) (b, bs)
          | a < b                 = LT
          | a > b                 = GT
          | length as < length bs = GT -- 差分枚数が同じならば
          | length as > length bs = LT -- 払う枚数が少ない方を優先
          | otherwise             = EQ

main = print $ pay 147 [(1, 2), (10, 4), (100, 3)]

短くしてみた。
%= のところでハイライトがおかしくなるのが悲しい。

def pay(e, h)
  h.default = 0
  h.each {|c,n| e -= c*n }
  raise "Money!" if (e *= -1) < 0
  [500,100,50,10,5,1].each do |c|
    h[c] -= e/c
    e %= c
  end
  h.reject {|c,n| n <= 0}
end

おお、短い。すばらしい！
でも……

pay(147, {1=> 2, 5=>300, 10=> 4, 100=> 3})
=> {5=>299, 1=>2, 100=>2}

すいません、意地悪で（苦笑

pay(147, {1=> 2, 5=>300, 10=> 4, 100=> 3})
=> {5=>299, 1=>2, 100=>2}

これあってますよね。
たぶん#73の方と同じ疑問点なのだと思いますが、

5 * 299 + 1 * 2 + 100 * 2 = 1697
1697 - 147 = 1550

でおつりは500 * 3, 50 * 1。確かに一番減ります。こんなお金の出され方したら怒りますけど（笑

Pythonでも同じアルゴリズムで書いてみました。

from operator import *
def pay(m, w):
  r = dict()
  m = sum((k*w[k] for k in w)) - m
  if m < 0: raise "money"
  for c in (500,100,50,10,5,1):
    r[c] = w.get(c, 0) - m / c
    m %= c
  return dict(((k,v) for k,v in r.items() if v > 0))

なるほど、端的に言うと例えば100円支払う時に100円玉を101枚渡せば
「店員は最も枚数が少なくなる返し方でおつりを返す」という条件から
1万円札が返ってくるわけですね。

問題条件にそう書いてある以上、
結果がいくら常識に反していても
「100円玉を101枚出す」が正解です。

出題が甘かったですね～(^^;

「やりとりする枚数が最小になるように」という条件にすればよかったのかもしれませんね…。

PHPで書いてみる。

<?php
function payment($price, $wallet){
	$coins = array('500' => 0, '100' => 0, '50' => 0, '10' => 0, '5' => 0, '1' => 0);
	$payment = pay($price, $wallet, $coins);
	foreach($coins as $coin=>$value){
		while($coin <= $payment['change']){
			$payment['change'] -= $coin;
			if($payment['coins'][$coin]){
				$payment['coins'][$coin]--;
			}
		}
	}
	return $payment['coins'];
}

function pay($price, $wallet, $coins){
	foreach($wallet as $coin=>$value){
		for($i = 0; $i < $value;$i++){
			$price -= $coin;
			$coins[$coin]++;
			if($price <=0){
				return array('coins'=>$coins,'change'=> - $price);
			}
		}
	}
	echo("お金が足りません");
}
$wallet = payment(147,array('1'=>2,'10'=>4,'100'=>3));
print_r($wallet);
?>

いろんな状況を考えてみたんですが、たぶん、可能なかぎり少額のコインを使うようにすると題意を満たすと思います。つまり、10円を払うとき、1円玉が10枚あるなら、10円玉があっても1円玉を使った方がよい。失敗するような意地悪な例題をもとむ。

$coins = [1, 5, 10, 50, 100, 500]

def changes(total)
  ret = {}
  $coins.sort_by{|a| -a}.each do |coin|
    if total >= coin
      num = total / coin
      total = total - coin * num
      ret[coin] = num
    end
  end
  ret
end

def pay(expence, wallet)
  total = 0
  payment = {}
  $coins.sort.each do |coin|
    next  unless wallet[coin]
    num = [(expence - total) / coin + 1, wallet[coin]].min
    payment[coin] = num
    total += coin * num
    break  if total >= expence
  end
  if total > expence
    change = changes(total - expence)
    change.each_pair do |coin, num|
      if payment.has_key?(coin)
        payment[coin] -= num
        payment.delete(coin) if payment[coin] <= 0
      end
    end
  end
  payment
end

# p pay(147, {1 => 2, 10 => 4, 100 => 3})

コード無しで質問なのですが、財布の中身が {100:10, 1:1} で支払うべき金額が 1 であった場合、期待される結果は {100 : 10} or {500 : 2} のどちらですか?

| 支払額 手持ち 支払 残高 |
支払額 := 147.
手持ち := 支払 := {1->2. 10->4. 100->3}
   inject: Bag new
   into: [:bag :assc | bag add: assc key withOccurrences: assc value; yourself].

残高 := 手持ち sum - 支払額.
#(500 100 50 10 5 1) do: [:コイン |
   | 枚数 |
   (枚数 := 残高 // コイン) > 0 ifTrue: [
      残高 := 残高 \\ (コイン * 枚数).
      枚数 timesRepeat: [支払 remove: コイン ifAbsent: []]]].
^支払 sortedElements asArray

"=> {1->2 . 100->2} "

差額に対する最小のコイン枚数を引いて出しています。あっているのか不明。

using System;
class Program
{
  static void Main()
  {
    int[] coins = { 1, 5, 10, 50, 100, 500 };
    int[] res = GetChange(coins, "1:2,10:4,100:3", 147);
    for (int i = 0; i < res.Length; ++i)
      if (res[i] > 0) Console.WriteLine("{0}:{1}", coins[i], res[i]);
  }
  static int[] GetChange(int[] coins, string data, int amo)
  {
    int[] nums = new int[coins.Length];
    int total = 0;
    foreach (string s in data.Split(','))
    {
      string[] ss = s.Split(':');
      int p = int.Parse(ss[0]);
      int n = int.Parse(ss[1]);
      nums[(int)Math.Log(p, 3)] = n;
      total += p * n;
    }
    int rem = total - amo;
    int[] res = new int[coins.Length];
    for (int i = res.Length - 1; i >= 0; --i)
      while (rem >= coins[i]) { rem -= coins[i]; ++res[i]; }
    for (int i = 0; i < res.Length; ++i)
      res[i] = Math.Max(0, nums[i] - res[i]);
    return res;
  }
}

iterate萌え。

(require :iterate)
(in-package :iterate)
(defparameter *coins* '(500 100 50 10 5 1))

;; DRY *coins*
(defun combinations (wallet)
  (labels ((cnt (coin) (or (cdr (assoc coin wallet)) 0)))
    (iter (for c0 from 0 to (cnt 500)) (appending
         (iter (for c1 from 0 to (cnt 100)) (appending
              (iter (for c2 from 0 to (cnt 50)) (appending
                   (iter (for c3 from 0 to (cnt 10)) (appending
                        (iter (for c4 from 0 to (cnt 5)) (appending
                             (iter (for c5 from 0 to (cnt 1)) (collecting
                                  (delete-if (lambda (cons) (zerop (cdr cons)))
                                             `((500 . ,c0) (100 . ,c1) (50 . ,c2) (10 . ,c3) (5 . ,c4) (1 . ,c5)))))))))))))))))

(defun amount (wallet)
  (iter (for (coin . cnt) in wallet) (sum (* coin cnt))))

(defun change (amount)
  (iter (for coin in *coins*)
        (with cnt)
        (unless (zerop (setf cnt (floor (/ amount coin))))
          (decf amount (* coin cnt))
          (collect (cons coin cnt)))))

(defun ways-to-pay (amount wallet)
  (let (changed-coins)
    (iter (for combination in (combinations wallet))
          (if (let ((change-amount (- (amount combination) amount)))
                (and (<= 0 change-amount)
                     (iter (for (c-coin . c-cnt) in (setf changed-coins (change change-amount)))
                           (always (null (assoc c-coin combination))))))
              (collect (list :pay combination :change changed-coins))))))

(defun count-coins (wallet)
  (iter (for (coin . cnt) in wallet) (sum cnt)))

;; wallet: alist
(defun pay (amount wallet)
  (iter (with coins-in-wallet = (count-coins wallet))
        (for way in (ways-to-pay amount wallet))
        (finding way minimizing (+ (- coins-in-wallet
                                      (count-coins (getf way :pay)))
                                   (count-coins (getf way :change))) into min)
        (finally (return (getf min :pay)))))

(pay 147 '((1 . 2) (10 . 4) (100 . 3))) ; => ((100 . 2) (1 . 2))

http://ja.doukaku.org/comment/63/と同様のアルゴリズムでやってみました。

#include <stdio.h>

typedef struct {
    int value; /* お金の価値 */
    int has;   /* 何枚持っているか */
} coin_data;

void pay(int expense, coin_data *pay_coin, coin_data *coin_case);

int main()
{
    int i;
    /* 始めに持っているお金 */
    coin_data coin_case[6] = {
        {  1, 2}, {  5, 300}, { 10, 4},
        { 50, 0}, {100, 3}, {500, 0},
    };
    /* 払うお金 */
    coin_data pay_coin[6] = {
        {  1, 0}, {  5, 0}, { 10, 0},
        { 50, 0}, {100, 0}, {500, 0},
    };

    for (i = 0; i < 6; i++) {
        printf("%d円玉 : %d枚\n", coin_case[i].value, coin_case[i].has);
    }
    pay(147, pay_coin, coin_case);
    for (i = 0; i < 6; i++) {
        printf("%d円玉 : %d枚\n", pay_coin[i].value, pay_coin[i].has);
    }

    return 0;
}

void pay(int expense, coin_data *pay_coin, coin_data *coin_case)
{
    int current_total;
    int i, j;

    current_total = 0;
    while (coin_case[5].has > 0) {
        current_total += coin_case[5].value;
        coin_case[5].has--;
        pay_coin[5].has++;
    }
    for (i = 4; i >= 0; i--) {
        while (coin_case[i].has > 0) {
            current_total += coin_case[i].value;
            coin_case[i].has--;
            pay_coin[i].has++;
        }
        while ((current_total - coin_case[i+1].value) >= expense
            && pay_coin[i+1].has > 0) {
            current_total -= coin_case[i+1].value;
            coin_case[i+1].has++;
            pay_coin[i+1].has--;
        }
    }
}

Scalaで。うーん、微妙・・・

import scala.collection.mutable.HashMap
import scala.collection.Map.Projection
def pay(money:Int, wallet:Map[Int, Int]):Projection[Int,Int] = {
  var m = money
  val r = new HashMap[Int,Int]
  m = wallet.keys./:(0){(r,k) => r+k*wallet(k)} - m
  if(m<0) throw new RuntimeException("Money!")
  List(500, 100, 50, 10, 5, 1).foreach(c => {
    r(c) = wallet.getOrElse(c, 0) - m/c
    m = m%c
  })
  r.filterKeys(k => r(k)>0)
}
pay(147, Map(1 -> 2, 5 -> 300, 10 -> 4, 100 -> 3)).foreach(p => print(p._1+":"+p._2+","))

「手持ちのコインを全て渡す」というのが答えですが、出したコインがそのまま帰ってくるような場合は
出さないようにしています。http://ja.doukaku.org/comment/60/ と同じですね・・・

> purse(pay=147, y1=2, y5=300, y10=4, y100=3)
  1   5 100 
  2 299   2 
> purse(pay=147, y1=2, y10=4, y100=3)
  1 100 
  2   2

purse <- function(pay=0, y500=0, y100=0, y50=0, y10=0, y5=0, y1=0){
    m   <- c(y500, y100, y50, y10, y5, y1)
    l   <- (names(m) <- c(500, 100, 50, 10, 5, 1))
    ret <- m %*% l - pay
    n   <- m - (ret %% c(ret+1, l[1:(length(l)-1)]) %/% l)
    print(rev(n[n>0]))
}

Prologが無いなんて許せません。
当然、全探索です。
制約論理を使えば、もっとスマートに行くのでしょうか…

coins([500,100,50,10,5,1]).

change(Sum,C):-coins(Coins),change(Coins,Sum,C).
change([],_,[]).
change([Co|Cos],Sum,C):-Co>Sum,change(Cos,Sum,C),!.
change([Co|Cos],Sum,[c(Co,C)|Cs]):-C is Sum // Co,Sums is Sum mod Co, change(Cos,Sums,Cs).

takeout([],[],[]).
takeout([c(Co,C)|Pos],Pa,R):-countUp(C,C1),plus(C2,C1,C),C1>=0,C2>=0,
                             (C1==0->Pa=Pas;Pa=[c(Co,C1)|Pas]),
                             (C2==0->R=Rs;R=[c(Co,C2)|Rs]),
                             takeout(Pos,Pas,Rs).

countUp(N,I):-countUp(N,0,I).
countUp(N,S,S):-S=<N.
countUp(N,S,I):-S<N,Ss is S + 1,countUp(N,Ss,I).

minCoin([A],[A]):-!.
minCoin([a(Ca,Pa)|As], B) :-
        minCoin(As, [a(C,P)|Ps]),
        (Ca<C->B=[a(C,P)];
               (Ca==C->B=[a(C,P),a(Ca,Pa)|Ps];
                       B=[a(C,P)|Ps])).

total([],0).
total([c(Co,C)|Cs],X):-total(Cs, Xs), X is Xs + Co * C.

try(Sum, Pocket, Pay, Rest, C) :-
        takeout(Pocket, Pay, Rest0),
        total(Pay, Total),
        Total >= Sum,
        plus(Change, Sum, Total),
        change(Change, Change0),
        diffCoin(Pay,Change0),
        appendCoin(Rest0,Change0,Rest),
        countCoin(Rest,C).

coinNumber(c(_,N),N).
coinName(c(N,_),N).

appendCoin([],X,X).
appendCoin([c(C,N)|Cs],R0,R):-appendCoinSub(C,N,R0,R1),appendCoin(Cs,R1,R).

appendCoinSub(C,N,[],[c(C,N)]).
appendCoinSub(C,N,[c(C,M)|Cs],[c(C,L)|Cs]):-L is N + M,!.
appendCoinSub(C,N,[Cx|Cs],[Cx|Rs]):-appendCoinSub(C,N,Cs,Rs).

diffCoin(X,Y):-maplist(coinName,X,Xn),maplist(coinName,Y,Yn),intersection(Xn,Yn,[]).

countCoin([],0).
countCoin([c(_,C)|Cs],X) :- countCoin(Cs,Xs), X is Xs + C.

findAns(Sum,Before,As):-findall(a(C,Pay),try(Sum,Before,Pay,_,C),As0),minCoin(As0,As).

:-findAns(147,[c(1,2),c(10,4),c(100,3)],A),writeln(A),halt.

頭の体操にとJavaScriptで。
アルゴリズムが正しいかどうかは正直自信ありません……。

javascript:function%20pay(pr,pu){var%20su=0,st=[],tk,ci;for(tk%20in%20pu)su+=tk*pu[tk];su=su-pr;if(su<0)return'short';for(ci=0;tk=[500,100,50,10,5,1,0][ci];ci++){var%20tc=pu[tk],nm=Math.floor(su/tk),tp=tc-nm;if(0<tp)st.unshift(tk+':'+tp);su-=tk*nm;}return'{'+st.join(',%20')+'}';}pay(147,{1:2,10:4,100:3})

function pay(m, w){
  function integer(a) if (a == null) 0 else int(a)
  r = map()
  n = 0
  for (k,v : w) n += k*v
  m = n - m
  if (m < 0) throw("not enough")
  for (c : [500, 100, 50, 10, 5, 1]){
     r[c] = integer(w[c]) - m/c
     m %= c
  }
  filter(r, {k,v -> v>0})
}
println(pay(147, {1=>2, 5=>300, 10=>4, 100=>3}))

全額渡してから、引き算してます。ずるい? お金が足りないときには、全額つき返されます。想定外。

def pay(price, wallet_coins) {
  def wallet = wallet_coins.collect { key, value ->
    key * value
  }.inject(0) { sum, value ->
    sum + value
  }

  def diff_coins = coins(wallet - price)
  subtract_coins(wallet_coins, diff_coins).findAll { key, value -> value > 0 }
}

def coins(price) {
  coins = [500,100,50,10,5,1].inject([:]) { sum, coin ->
    if(price >= coin) {
      def count = (price / coin).toBigInteger()
      price = price - coin*count
      sum[coin] = count
    }
    sum
  }
}

def subtract_coins(xs,ys) {
  [500,100,50,10,5,1].inject([:]) { result, coin ->
    xcount = xs[coin] == null ? 0 : xs[coin]
    ycount = ys[coin] == null ? 0 : ys[coin]
    result[coin] = xcount - ycount
    result
  }
}

println pay(147, [1:2, 10:4, 100:3])
println pay(147, [1:2, 10:4, 100:1])

同じ種類の硬貨を20枚以上指定しても、20枚までしか使わないように制限してあります。
関数 pay(amount, coins, result) は金額(amount)と所持する硬貨の枚数の配列(coins)を受け取り、おつりを受け取った後のコインの数が最も少なくなる組み合わせ(result)を返します。

% awk -f otsuri.awk
147 0 3 0 4 0 2
100x2 1x2 (2枚減)
147 1 1 1 1 1 147
100x1 50x1 1x17 (17枚減)※同じ種類の硬貨を一度に使えるのは20枚まで
147 0 0 0 0 0 0
持ち金不足

{
	amount = $1

	coins[500] = $2
	coins[100] = $3
	coins[50] = $4
	coins[10] = $5
	coins[5] = $6
	coins[1] = $7

	if (amount > coins[1] + 5*coins[5] + 10*coins[10] + 50*coins[50] + 100*coins[100] + 500*coins[500]) {
		print "持ち金不足"
		next
	}

	limitted = 0
	if (coins[500] > 20 || coins[100] > 20 || coins[50] > 20 || coins[10] > 20 || coins[5] > 20 || coins[1] > 20) {
		limitted = 1
		if (coins[500] > 20) coins[500] = 20
		if (coins[100] > 20) coins[100] = 20
		if (coins[50] > 20) coins[50] = 20
		if (coins[10] > 20) coins[10] = 20
		if (coins[5] > 20) coins[5] = 20
		if (coins[1] > 20) coins[1] = 20
	}

	# 計算〜結果表示
	pay(amount,coins, result)

	if (result[500]) printf("500x%d ", result[500])
	if (result[100]) printf("100x%d ", result[100])
	if (result[50]) printf("50x%d ", result[50])
	if (result[10]) printf("10x%d ", result[10])
	if (result[5]) printf("5x%d ", result[5])
	if (result[1]) printf("1x%d ", result[1])

	if (result["diff"] == 0) printf("(枚数の増減なし)")
	else if (result["diff"] < 0) printf("(%d枚減)", -result["diff"])
	else printf("(%d枚増)", result["diff"])

	if (limitted) print "※同じ種類の硬貨を一度に使えるのは20枚まで"
	else printf "¥n"
}

function pay(amount,coins,result, i,j,k,l,m,n,
			 coins_out,coins_out_amount,change,
			 coins_in,coins_diff,coins_diff_minimum,coins_diff_minimum_at)
{
	coins_diff_minimum = 999999
	coins_diff_minimum_at = ""

	if (coins[1] < 1) coins[1] = 0
	if (coins[5] < 1) coins[5] = 0
	if (coins[10] < 1) coins[10] = 0
	if (coins[50] < 1) coins[50] = 0
	if (coins[100] < 1) coins[100] = 0
	if (coins[500] < 1) coins[500] = 0

	for (i=0; i<=coins[1]; i++) {
		for (j=0; j<=coins[5]; j++) {
			for (k=0; k<=coins[10]; k++) {
				for (l=0; l<=coins[50]; l++) {
					for (m=0; m<=+coins[100]; m++) {
						for (n=0; n<=coins[500]; n++) {
							# 出て行く枚数
							coins_out = i + j + k + l + m + n
							# 出て行く金額
							coins_out_amount = i + j*5 + k*10 + l*50 + m*100 + n*500
							if (coins_out_amount < amount) continue

							# お釣り
							change = coins_out_amount - amount
							# お釣りの枚数を数える
							coins_in = count_coins(change,change_coins)
							# 枚数の差分
							coins_diff = coins_in - coins_out

							# 支払額が異常に多いケースを排除
							if (n == 0) { # 500円玉を使っていない
								if (change_coins[500] > 0) continue # のに釣り銭に500円玉が入っている
								else if (m == 0) { # 100円玉も使っていない
									if (change_coins[100] > 0) continue # のに釣り銭に100円以上の硬貨が入っている
									else if (l == 0) { # 50円玉も使っていない
										if (change_coins[50] > 0) continue # のに釣り銭に50円以上の硬貨が入っている
										else if (k == 0) { # 10円玉も使っていない
											if (change_coins[10] > 0) continue # のに釣り銭に10円以上の硬貨が入っている
											else if (j == 0) { # 5円玉も使っていない
												if (change_coins[5] > 0) continue # のに釣り銭に5円以上の硬貨が入っている
											}
										}
									}
								}
							}

							# 自分が払ったのと同種のコインが戻って来る組み合わせは排除
							if (i > 0 && change_coins[1] > 0) continue
							if (j > 0 && change_coins[5] > 0) continue
							if (k > 0 && change_coins[10] > 0) continue
							if (l > 0 && change_coins[50] > 0) continue
							if (m > 0 && change_coins[100] > 0) continue
							if (n > 0 && change_coins[500] > 0) continue

							# 新記録。同値の場合は最初に現れた組み合わせが記録される
							if (coins_diff < coins_diff_minimum) {
								coins_diff_minimum = coins_diff
								coins_diff_minimum_at = i "," j "," k "," l "," m "," n
							}
						}
					}
				}
			}
		}
	}

	# 結果を result[] に収める
	delete result
	split(coins_diff_minimum_at, ar, ",")
	if (ar[1] > 0) result[1] = ar[1]
	if (ar[2] > 0) result[5] = ar[2]
	if (ar[3] > 0) result[10] = ar[3]
	if (ar[4] > 0) result[50] = ar[4]
	if (ar[5] > 0) result[100] = ar[5]
	if (ar[6] > 0) result[500] = ar[6]
	
	result["diff"] = coins_diff_minimum # 枚数の増減（減ったら負）
}

function count_coins(amount,change_coins)
{
	delete change_coins

	if (amount >= 500) { 
		change_coins[500] = int(amount / 500)
		amount -= 500 * change_coins[500]
	}
	if (amount >= 100) {
		change_coins[100] = int(amount / 100)
		amount -= 100 * change_coins[100]
	}
	if (amount >= 50) {
		change_coins[50] = int(amount / 50)
		amount -= 50 * change_coins[50]
	}
	if (amount >= 10) {
		change_coins[10] = int(amount / 10)
		amount -= 10 * change_coins[10]
	}
	if (amount >= 5) {
		change_coins[5] = int(amount / 5)
		amount -= 5 * change_coins[5]
	}
	if (amount >= 1)
		change_coins[1] = amount

	return change_coins[500] + change_coins[100] + change_coins[50] + change_coins[10] + change_coins[5] + change_coins[1]
}

この問題は、実際にお店で行われるやり取りを想定したものですよね？ということで
「渡した硬貨がおつりで返ってくるような渡し方は禁止」を
「渡した硬貨が両替されて返ってくるような渡し方は禁止」と読み替えてやってみました☆
C言語は不慣れなのでごちゃごちゃですが題意は満たしていると思います☆

#include<stdio.h>
void pay(int price,int y0,int y1,int y2,int y3,int y4,int y5,int y6,int y7,int y8){
  int possession[]={y0,y1,y2,y3,y4,y5,y6,y7,y8},
      denomination[]={1,5,10,50,100,500,1000,5000,10000},
      i,j;
      //表示。
      printf("支払額 = %d\n金種　　",price);
      for(i=0;i<9;i++)
        printf("%6d",denomination[i]);
      printf("\n所持枚数");
      for(i=0;i<9;i++)
        printf("%6d",possession[i]);
      //所持枚数を元に支払額を補正（繰上げ）。
      for(j=0,i=0;i<9;i++){
        j+=denomination[i]*possession[i];
        if(i<8&&price%denomination[i+1]>j)
          price=price-price%denomination[i+1]+price%denomination[i]+denomination[i+1];
      }
      //補正された支払額を元に支払枚数を算出。
      for(price=j-price,i=8;i>=0;i--)
        if(possession[i]>0&&price>=denomination[i])
          possession[i]--,
          price-=denomination[i],
          i++;
      //表示。
      printf("\n支払枚数");
      for(i=0;i<9;i++)
        if(price>=0)
          printf("%6d",possession[i]);
        else
          printf(" -----");
      printf("\n\n");
}
int main(void){
  pay(  147,  3,  0,  5,  0,  1,  0,  0,  0,  0);
  pay(  147,  2,300,  4,  0,  3,  0,  0,  0,  0);
}

#1700 のコメントの方法をそのまま移植しました。

import java.util.TreeMap;

public class Sample {
    public static void main(String[] args) {
        TreeMap<Integer, Integer> purse = new TreeMap<Integer, Integer>();
        purse.put(1, 2);
        purse.put(10, 4);
        purse.put(100, 3);
        purse.put(500, 5);
        System.out.println(pay(147, purse));
    }

    public static TreeMap<Integer, Integer> pay(int price,
            TreeMap<Integer, Integer> purse) {
        TreeMap<Integer, Integer> pay = new TreeMap<Integer, Integer>();
        int n = 0;
        for (int coin : purse.keySet()) {
            n += coin * purse.get(coin);
        }
        price = n - price;
        if (price < 0) {
            throw new IllegalArgumentException("Not enough");
        }
        for (int coin : new int[]{500, 100, 50, 10, 5, 1}) {
            int m = (purse.get(coin) != null) ? purse.get(coin) : 0;
            pay.put(coin, m - price / coin);
            price %= coin;
        }
        for (int coin : new int[]{500, 100, 50, 10, 5, 1}) {
            if (pay.get(coin) <= 0) {
                pay.remove(coin);
            }
        }
        return pay;
    }
}

#2566(#1700)の方法は、以下のような非常に巧みなやり方です。
支払い後の金額を正規化（コインの枚数が最少に）するため、正規化した枚数から現在所持している枚数を引くと正の枚数が支払い枚数、負の枚数がお釣りの枚数になる。

これはほとんどの場合うまくいくのですが、元々の所持金の枚数が著しく偏っていた場合、10円を20枚出して100円を2枚釣りにもらうという普通はやらないような支払い方を行ってしまいます（このような支払い方法を仮に両替的支払いと呼びます）。もちろん、支払い後の枚数を強制的に正規化しようとするのが原因です。

この払い方でも題意は満たしていると思えるのですが、気になったので両替的支払いを行わないように修正してみました。

両替的支払いを以下のように定義します。
・支払ったコインの最高額が釣りの金額を超える支払い方法

import java.util.TreeMap;

public class Sample {
    public static void main(String[] args) {
        TreeMap<Integer, Integer> purse = new TreeMap<Integer, Integer>();
        purse.put(1, 4);
        purse.put(10, 4);
        purse.put(100, 3);
        System.out.println(pay(147, purse));
    }

    public static TreeMap<Integer, Integer> pay(int price, 
            TreeMap<Integer, Integer> purse) {
        TreeMap<Integer, Integer> pay = new TreeMap<Integer, Integer>();
        int n = 0;
        for (int coin : purse.keySet()) {
            n += coin * purse.get(coin);
        }
        price = n - price;
        if (price < 0) {
            throw new IllegalArgumentException("Not enough");
        }
        int changeVal = 0;
        boolean change = true;
        for (int coin : new int[]{500, 100, 50, 10, 5, 1}) {
            int m = (purse.get(coin) != null) ? purse.get(coin) : 0;
            m -= price / coin;
            if (change && m < 0) {
                changeVal -= m * coin;
            }
            if (m > 0 && changeVal > 0) {
                if (m * coin >= changeVal) {
                    m -= changeVal / coin;
                    changeVal %= coin;
                } else {
                    changeVal -= m * coin;
                    m = 0;
                }
            }
            if (m > 0) {
                pay.put(coin, m);
                change = false;
            }
            price %= coin;
        }
        return pay;
    }
}

両替的支払いの定義が間違っていました。もちろん
・釣りの金額が支払ったコインの最高額を超える支払い方法
が正しいです。

Java の処理系が入ってないから実行してないけど、そのコードおかしいよ。
むしろバグバグになったようにしか見えない。

#2556(#1700)で直すべきなのは

1. 26行目 m - price / coin (9行目 r[c] = integer(w[c]) - m/c)
2. 27行目 price %= coin (10行目 m %= c)
3. 29-33行目(12行目 filter(r, {k,v -> v>0}))

の3箇所で、それぞれ (k = min {m, price/coin} として)

1. m - k
2. price -= coin * k
3. 削除

に置き換えるべきなんだと思うぞ。

というわけでそれを Haskell で書いてみた。
ついでにこのお題に投稿されてるコードはバグってるのだらけ
(両替的支払いがいいならそんなことないか)のようなので、説明してみる:

大きい価格のコインから順に、払う枚数を必要最小限になるように決めていく。

なにをもって必要最小限と判断するかというと、
余分(extra (#2556, #1700 ではそれぞれ price と m))、
つまり必要の無い支払いというのを考え、余分の範囲内で、
できるだけ払うコインを減らす。

最初の時点では

余分 = 財布の中身全額 - 支払い

となっている。余分の範囲で(減らそうとしてる)できるだけ多い枚数ってのが
extra `div` c (price / coin や m / c)。

しかし、これだと例えば100円玉を100毎ぐらい持ってて、余分な額が1万近いときに、
500円玉を3枚しか持ってないのに500円玉18枚ぐらい余分とか言われてしまう。そして

払う枚数 (n-k や m - price / coin や integer(w[c]) - m/c)
= 必要な枚数 = 持ってる枚数 - 余分な枚数

なのでそのままではマイナス枚払うことになる。つまり受け取る。
その分小さいコインを払う。両替的支払い。

だから、持ってる枚数以上を余分な枚数としないように

余分な枚数 (k) = min {持ってる枚数, さっき言ってた余分な枚数}

とする。これで、

支払う枚数 = 持ってる枚数 - k

とし、また余分な k 枚だけ c 円のコインの支払いを減らしたわけだから

新しい余分な額 = 余分な額 - k * c

として、より小額のコインに対し今やったのを繰り返していけばよい。

import Data.List (sortBy)

amount :: [(Int,Int)] -> Int
amount = sum . map (uncurry (*))

pay :: Int -> [(Int,Int)] -> [(Int,Int)]
pay expense wallet
 | extra < 0 = error "you need more money!"
 | otherwise = adjust extra (descend wallet)
 where
  extra = amount wallet - expense
  descend = sortBy (flip compare)
  adjust _ [] = []
  adjust extra ((c,n):w) = (c,n-k) : adjust (extra-k*c) w
   where k = min n (extra `div` c)

あれ？お題で示されている例題を食わせると
*Main> pay 147  [(1,2),(10,4),(100,3)]
[(100,2),(10,0),(1,0)]
となりますが、これが意図した解でしょうか？

あー、なんかそれも変ですね。

前にこの問題考えたとき、結局よくわからなかったんだけど、
やっぱり今回もわかってなかったか…。バカ…。

バグっているというよりは、「両替的支払い」を正しく定義できていないのです。正しい定義をして作り直すつもりなのですが、まだ途中なので発表できていません。もう少しお待ちください。

ちなみに正しい定義は、今のところ、次のようになるのではないかと考えています。

両替的支払い：小額のコインを多数支払う事によって高額のコインをお釣りにもらうような支払い方法

「支払ったコイン一式があったとき、お釣りを両替できてはいけない」
という条件でよさそうですが、どうでしょうか。(あんまり深く考えてないけど。。。)

先の条件を満して手持ちのコイン数が最小になる支払い。

うーん。美しさがない定義ですね。だめか。。。

支払ったコインの集合をxs、受け取ったコインの集合をysとした時、
「ysの任意の部分集合(空でない)と同じ金額になるxsの部分集合があってはいけない」
というのではどうでしょう。

基本的に

http://ja.doukaku.org/comment/63/

のport.

Dan the Perl Monger

#!/usr/local/bin/perl
use strict;
use warnings;
my @coins = qw/1 5 10 50 100 500/;

sub changes{
    my $total = shift;
    my %ret;
    for my $coin (reverse @coins){
        next unless $total >= $coin;
        my $num = int($total/$coin);
        $total = $total - $coin * $num;
        $ret{$coin} = $num;
    }
    \%ret;
}

sub min{ $_[0] < $_[1] ? $_[0] : $_[1] };

sub pay{
    my ($expense, $wallet) = @_;
    my $total = 0;
    my %payment;
    for my $coin (@coins){
        next unless $wallet->{$coin};
        my $num = min(int(($expense-$total)/$coin + 1), $wallet->{$coin});
        $payment{$coin} = $num;
        $total += $coin * $num;
        last if $total >= $expense;
    }
    return \%payment unless $total > $expense;
    my $change = changes($total - $expense);
    while(my ($coin, $num) = each %$change){
        next unless $payment{$coin};
        $payment{$coin} -= $num;
        delete $payment{$coin} if $payment{$coin} <= 0;
    }
    \%payment;
}

use Data::Dumper;
print Dumper (pay(147, {1 => 2, 10 => 4, 100 => 3}))

http://codepad.org/DKipsErM
pay(147, {1=> 11, 5=> 2, 10=> 1, 100=> 3})
結果:
$VAR1 = {
          '1' => 7,
          '100' => 2,
          '5' => 2
        };

Perl、Rubyで投稿されてるのをPHPに移植してみましたバージョン。
foreachが使えるところはPHPが便利だけど、delete, next unless処理はPHPだとダサいような。。

see: http://ja.doukaku.org/comment/63/

<?php

$coins = array(1, 5, 10, 50, 100, 500);

function changes($total)
{
    global $coins;
    $ret = array();
    foreach(array_reverse($coins) as $coin) {
        if($total >= $coin) {
            $num = intval($total / $coin);
            $total = $total - $coin * $num;
            $ret[$coin] = $num;
        }
    }
    return $ret;
}
function pay($price, $wallet)
{
    global $coins;
    $total = 0;
    $payment = array();
    foreach ($coins as $coin) {
        if(!empty($wallet[$coin])) {
            $num = min(intval($price-$total/$coin+1), $wallet[$coin]);
            $payment[$coin] = $num;
            $total += $coin * $num;
            if( $total >= $price){ break; }
        }
    }
    if($total > $price) {
        $change = changes($total - $price);
        foreach($change as $coin => $num) {
            if(!empty($payment[$coin])) {
                $payment[$coin] -= $num;
                if($payment[$coin] <= 0) { unset($payment[$coin]); }
            }
        }
    }
    return $payment;
}
//pay( 147, array("1" => 2, "10" => 4, "100" => 3));
?>

金額の小さいお金から、できるだけ多く払うようにしています。
どうでしょうか？
エラーチェックは最小限です。
以下実行例:
gosh> (pay-smart 147 '((1 . 2) (10 . 4) (100 . 3)))
((100 . 2) (1 . 2))

内容解説:
6 - 8: 手持ちのお金で払えるかをチェック
10～: 支払い関数 引数: 支払い金額、手持ちのお金(硬貨の額、枚数のペア のリスト)、払う硬貨入れ
12: m <- 硬貨の額
13: n <- 硬貨の枚数
14: b <- 次の硬貨の金額になる枚数(1 円なら 5 枚で 5 円、5 円なら 2 枚で 10 円)
15: pay2 <- この硬貨にとっての端数を埋める(10 円玉の支払い順の時に、支払残高が 15 円になっている場合に 5 円埋めて 残高を 20 円にする)
16: amari <- この硬貨を支払い後、何枚余るか(支払残高 14 円に対して 1 円を 7 枚持っている場合、4 枚払って 3 枚余り。この 3 という数字)
17-18: 硬貨が実在するものかをチェック。53 円玉なんて存在しない
20: 残高 <= 金額 * 枚数 -> 全額支払い終了
21-23: 余り < 枚数 -> 支払い可能。"枚数 - 余り" の枚数の硬貨を支払って(支払い残高から引いて)次の硬貨の処理へ
24: 余り > 枚数 -> 支払い不可。そのまま次の硬貨の処理へ

amari の算出方法はもっとどうにかならんものか。

(define pay-smart
  (lambda (pay money)
    (if (not (canpay? pay money)) (error "お金足りてません"))
    (do-paying pay (sort money (lambda (x y) (< (car x) (car y)))) '())))

(define canpay? 
  (lambda (pay money)
    (if (<= pay (apply + (map (lambda (ls) (* (car ls) (cdr ls))) money))) #t #f)))

(define do-paying
  (lambda (pay money ls)
    (let* ((m (caar money))
           (n (cdar money))
           (b (if (memq m '(5 50 500)) 2 5))
           (pay2 (let1 tmp (modulo pay m) (if (or (= m 1) (= 0 tmp)) pay (+ pay (- m tmp)))))
           (amari (modulo (- b (modulo (- (/ pay2 m) n) b)) b)))
      (if (not (memq m '(1 5 10 50 100 500)))
          (error (format #f "~d 円という硬貨はありません" m))
      (cond 
       ((<= pay2 (* m n)) (cons (cons m (/ pay2 m)) ls))
       ((> n amari) (do-paying (- pay2 (* m (- n amari)))
                               (cdr money) 
                               (cons (cons m (- n amari)) ls)))
       (else (do-paying pay2 (cdr money) ls)))))))

gosh> (pay-smart 14 '((1 . 12) (10 1)))
((10 . 1) (1 . 9))

(1 . 4) であってほしい。

#!/usr/bin/perl
use strict;
use Data::Dumper;

print Dumper(pay(147,(1 => 2, 10 => 4, 100 => 3)));

sub pay{
        my ($pay,%input) = @_;
        my @money = qw(1 5 10 50 100 500);
        my $total = 0;
        my %rtn = ();

        TOTAL:
        for my $key (@money){
                for (1 .. $input{$key}){
                        $total += $key;
                        $rtn{$key}++;
                        last TOTAL if($total >= $pay);
                }
        }

        CHANGE:
        for my $key (reverse @money){
                while($total - $pay >= $key){
                        $total -= $key;
                        delete($rtn{$key}) if(--$rtn{$key} <= 0);
                        last CHANGE if($total <= $pay);
                }
        }

        return \%rtn;
}

print Dumper(pay(147,(1 => 13, 100 => 2)));
$VAR1 = {
          '1' => 12,
          '100' => 2
        };

7枚が正しいのでは。

#63の写経です。

see: http://ja.doukaku.org/comment/63/

#!/bin/bash
readonly coins='1 5 10 50 100 500'
readonly coins_rev='500 100 50 10 5 1'

function changes() {
    local -i total=$1
    local -i coin num
    for coin in $coins_rev; do
        if ((total >= coin)); then
            ((num = total / coin, total = total - coin * num))
            echo -n "$coin=$num "
        fi
    done
}

function pay() {
    local -i expence=$1
    local wallet=$2
    local -i total=0 coin num
    local item var

    for item in $wallet; do
        eval local wallet_$item
        eval local payment_${item%=*}
    done

    for coin in $coins; do
        var=wallet_$coin
        if [ -n "${!var}" ]; then
            local -i r=$(((expence - total) / coin + 1))
            ((num = r < ${!var} ? r : ${!var}))
            eval payment_$coin=$num
            ((total += coin * num))
            ((total >= expence)) && break
        fi
    done

    if ((total > expence)); then
        for item in $(changes $((total - expence))); do
            eval coin=${item/=/;num=}
            var=payment_$coin
            if [ -n "${!var}" ]; then
                eval "(($var -= num))"
                ((${!var} <= 0)) && unset $var
            fi
        done
    fi

    for var in ${!payment_*}; do
        echo -n "${var#payment_}=${!var} "
    done
    echo
}

pay 147 '1=2 10=4 100=3'

DouKaku?

コインを減らす払い方

Posted feedbacks - Nested

Index

Feed

Other

Link

Pathtraq