2015年04月22日

C#で手持ちのコインを減らす払い方を求める

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その86

■問題 (出題者:不明)
いま、あなたの財布の中にはコインがたくさん入っています。これを少しでも減らしたいと思います。
支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。
例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。


問題には、コインとあるが、1円玉から1万円札まで扱えるようにしてみる。
なお、渡したお金が返ってくるような渡し方は禁止することとする。
これは、このシリーズでこれまでに解いてきた問題の中で、一番梃子摺った問題だ。

まずは Walletクラスを作成。
初期バージョン

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NewVersion {
    class Wallet {
        public SortedDictionary<int, int> Coins { get; private set; }

        public Wallet() {
            Coins = new SortedDictionary<int, int>();
        }

        public Wallet(int yen1, int yen5, int yen10, int yen50, int yen100, int yen500,
                         int yen1000 = 0, int yen5000 = 0, int yen10000 = 0)
            : this() {
            Coins[1] = yen1;
            Coins[5] = yen5;
            Coins[10] = yen10;
            Coins[50] = yen50;
            Coins[100] = yen100;
            Coins[500] = yen500;
            Coins[1000] = yen1000;
            Coins[5000] = yen5000;
            Coins[10000] = yen10000;
        }

        public int Amount() {
            return Coins.Sum(x => x.Key * x.Value);
        }

        public int Count() {
            return Coins.Sum(x => x.Value);
        }

        public void Print() {
            foreach (var x in Coins.Reverse()) {
                Console.Write("{0}:{1} ", x.Key, x.Value);
            }
            Console.Write("=> {0:#,0}円, {1}枚", Amount(), Count());
            Console.WriteLine();
        }
    }
}

合計がいくらなのか Amountメソッドとコイン(札も含める)の枚数は何枚なのかを求める Countメソッドを作成。
コンストラクタの引数の数が多すぎるような気がするが、今回はこれで妥協する。
なお以降の説明では便宜上コインには札も含めることとする。

それと、財布の中を表示する Print()メソッドも定義しておいた。

まだ具体的に問題は考えていないが、たぶん、50円を1枚支払うといった処理が必要になりそうだ。
ただ、50円玉が無い場合もあるので、支払えたら true、支払えなかったらfalseを返すようにしてみよう。

書いたメソッドは以下の通り。もちろん、Walletクラスのメソッドとして定義する。

private bool PayOneUnit(int coinType) {
    if (Coins[coinType] <= 0)
        return false;
    Coins[coinType]--;
    return true;
}

さて、これができれば、今度は、10円を7枚支払うとか、50円を3枚支払うとかの機能が 実装できそうだ。

public bool PayPart(int coinType, int count) {
    var save = this.Clone();
    for (int i = 0; i < count; i++) {
        if (!PayOneUnit(coinType)) {
            Coins = save.Coins;
            return false;
        }
    }
    return true;
}

private Wallet Clone() {
    var obj = new Wallet();
    obj.Coins = new SortedDictionary<int, int>(this.Coins);
    return obj;
}

for文で繰り返しPayOneUnitを呼び出しているだけなので、単純なコードだ。
支払えなかったときに、財布の状態が変化しないように、Cloneメソッドを定義し、 元に戻すようにしている。

さて、これでだいぶ準備が整ってきたと思う。
それでは、問題を解くメソッドを書くことにする。
最初に書いたときは、1円の位、10円の位、100円の位と処理をしていたので、 5円,50円,500円の特別処理が必要だったけど、よくよく考えてみると、以下に示すように そんな個別処理を書かなくても、大丈夫だった。

実際に自分がどうやって支払っているかを考えてみる。
例えば、183円を支払うとする。
順に、1円を出せるか、5円を出せるか、10円を出せるか、50円を出せるか... とやっていけばよい。
つまり、1円を3枚出す。次に10円が3枚出す、50円を1枚出す、100円を1枚出せばよい。
しかし、出せない場合もあ。その場合は繰り上げ処理を行うことになる。
例えば、10円が2枚しかなければ、30円の支払いは行わずに次の硬貨の50円の支払いに繰り上げる。
なので、すでに3円を出しているとすれば、180-30-50=200 で200円の支払いの処理に置き換えるわけである。
さらに100円硬貨が1枚しか手元になければ、500円に支払いに繰り上げる。つまり 200-200+500 で、500円を支払う、さらに500円硬貨もなければ、500円にの支払いはせずに、次に大きい1000円の 支払いに繰り上げる。これをどんどん繰り返していけばよい。

このやり方をコードにしたのが以下のメソッドである。

public Wallet Pay(int payment) {
    if (this.Amount() < payment)
        return null;
    var save = this.Clone();
    int paid = 0;
    int workPayment = payment;
    foreach (var coinType in _coinTypes) {
        int nextType = NextCoinType(coinType);
        int currPayment = workPayment % nextType;
        if (PayPart(coinType, currPayment / coinType)) {
            paid += currPayment;
        } else {
            // 繰上げ処理
            workPayment += nextType;
        }
        workPayment -= currPayment;
        if (paid >= payment)
            break;
    }
    return save.Subtract(this);
}

private static int GetIndex(int coinType) {
    return Array.FindIndex(_coinTypes, x => x == coinType);
}

private static int NextCoinType(int coinType) {
    int index = GetIndex(coinType) + 1;
    if (index < _coinTypes.Length)
        return _coinTypes[index];
    else
        return 100000;
}

public Wallet Subtract(Wallet b) {
    var work = new Wallet();
    foreach (var currency in _coinTypes)
        work.Coins[currency] = this.Coins[currency] - b.Coins[currency];
    return work;
}

なお、_coinTypes というフィールドも新たに追加している。

private static int[] _coinTypes = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };

Payメソッドは、Walletオブジェクトを返すが、これは、支払うコインだけをWalletに入れたものを 返している。
Payメソッドが呼ばれると、自分自身のCoinsの値は更新され、支払った分だけが減っている。
このとき、おつりはまだ受け取っていないという状態である。
NextCoinTypeは、現在よりも一つ大きいコインを返すのだが、1万円が渡された場合は 便宜上、10万円を返している。5万円でも別に問題はない。

これで、動かしてみる。

int payment = 183;
Wallet bag = new Wallet(3, 1, 4, 1, 3, 0, 2, 1, 2);
bag.Print();

var paid = bag.Pay(payment);
paid.Print();

結果を以下に示す。

10000:2 5000:1 1000:2 500:0 100:3 50:1 10:2 5:1 1:3 => 27,378円, 15枚
10000:0 5000:0 1000:0 500:0 100:2 50:0 10:0 5:0 1:3 => 203円, 5枚

上が支払う前のWalletの内容、下が支払ったコインの内容だ。
この例はうまく動いている。では次の例はどうだろうか?

int payment = 183;
Wallet bag = new Wallet(3, 1, 2, 2, 3, 0, 2, 1, 2);
bag.Print();

var paid = bag.Pay(payment);
paid.Print();

10000:2 5000:1 1000:2 500:0 100:3 50:2 10:2 5:1 1:3 => 27,428円, 16枚
10000:0 5000:0 1000:0 500:0 100:2 50:0 10:0 5:0 1:3 => 203円, 5枚

同じ183円の支払いだが、最初の財布の中身が異なる。
本来ならば、50円を2枚出してほしいのだが、50円を出さずに100円を出してしまっている。
これはだめだ。
1円が13枚あれば、それを全部出してほしいところだが、残念ながら、そういったコードには なっていない。

そこで改良したのが以下のコード。
Payメソッドはそのままとし、下位メソッドである PayOneUnit に手を入れている。

これは、コインを1枚支払うメソッドということだが、もし、それよりも小さなコインで 支払えれば、そっちで支払うというものだ。
これを再帰で書いている。


private bool PayOneUnit(int payment, int currCoineType = 1) {
    if (payment == 0)
        return true;          // ぴったり払えた!
    var coins = _coinTypes.SkipWhile(x => x < currCoineType).TakeWhile(x => x <= payment);
    foreach (var coinType in coins) {
        if (payment % coinType != 0)
            break;  // 絶対にぴったりの支払いは無理。無駄な探索を打ち切る
        if (Coins[coinType] > 0) {
            Coins[coinType]--;
            payment -= coinType;
            bool r = PayOneUnit(payment, coinType);
            if (r == true)
                return true;
            Coins[coinType]++;
            payment += coinType;
        }
    }
    return false;
}

では、実行してみる。
ここでは、5円硬貨を沢山持っている例。

int payment = 247;
Wallet bag = new Wallet(2, 6, 6, 0, 3, 0, 2, 1, 2);
bag.Print();

var paid = bag.Pay(payment);
paid.Print();

10000:2 5000:1 1000:2 500:0 100:3 50:0 10:6 5:6 1:2 => 27,392円, 22枚
10000:0 5000:0 1000:0 500:0 100:2 50:0 10:2 5:5 1:0 => 245円, 9枚

ちゃんと5円硬貨を出してくれていることが分かる。

次に、実際にはおつりをもらうわけだから、その処理を書いてみる。
この場合は、常にコインは十分に用意してあるという前提だ。

public static Wallet Normalize(int amount) {
    var work = new Wallet();
    var workAmount = amount;
    foreach (var coinType in _coinTypes) {
        int nextType = NextCoinType(coinType);
        int amari = workAmount % nextType;
        work.Coins[coinType] = amari / coinType;
        workAmount -= amari;
    }
    return work;
}

最初はおつりを支払うという意味の名前にしようかと思ったのだが、 ここは、あえて、Normalizeという名前にした。金種表作る際にこの手のコードが使えますね。
やはり、戻り値はWalletだ。こうなると、Walletの名前が不適切になってくるが、 このままとする。

このおつりを財布に戻さないといけないので、Addメソッドも定義する。

public Wallet Add(Wallet b) {
    var work = new Wallet();
    foreach (var currency in _coinTypes)
        work.Coins[currency] = this.Coins[currency] + b.Coins[currency];
    return work;
}

これらのメソッドを使った例を以下に示す。


int payment = 3288;
Wallet bag = new Wallet(2, 6, 6, 0, 3, 0, 2, 1, 2);
bag.Print();

// 支払う
var paid = bag.Pay(payment);
paid.Print();

// おつりを求める
Wallet change = Wallet.Normalize(paid.Amount() - payment);
change.Print();

// おつりを財布に戻す
Wallet newBag = bag.Add(change);
newBag.Print();


10000:2 5000:1 1000:2 500:0 100:3 50:0 10:6 5:6 1:2 => 27,392円, 22枚
10000:0 5000:1 1000:0 500:0 100:2 50:0 10:6 5:6 1:0 => 5,290円, 15枚
10000:0 5000:0 1000:2 500:0 100:0 50:0 10:0 5:0 1:2 => 2,002円, 4枚
10000:2 5000:0 1000:4 500:0 100:1 50:0 10:0 5:0 1:4 => 24,104円, 11枚

最後に、Wallletの全体を掲載しなおす。
クラス名は、SmartWalletとかにして、Payなどの戻り値、Subtractなどの引数は、 IDictionary < int, int > にしても良かったかも。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Wallet {
        public SortedDictionary<int, int> Coins { get; private set; }
        private static int[] _coinTypes;

        public Wallet() {
            Coins = new SortedDictionary<int, int>();
        }

        public Wallet(int yen1, int yen5, int yen10, int yen50, int yen100, int yen500,
                         int yen1000 = 0, int yen5000 = 0, int yen10000 = 0)
            : this() {
            Coins[1] = yen1;
            Coins[5] = yen5;
            Coins[10] = yen10;
            Coins[50] = yen50;
            Coins[100] = yen100;
            Coins[500] = yen500;
            Coins[1000] = yen1000;
            Coins[5000] = yen5000;
            Coins[10000] = yen10000;
            _coinTypes = Coins.Keys.ToArray();  // = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };
        }

        public int Amount() {
            return Coins.Sum(x => x.Key * x.Value);
        }

        public int Count() {
            return Coins.Sum(x => x.Value);
        }

        public void Print() {
            foreach (var x in Coins.Reverse()) {
                Console.Write("{0}:{1} ", x.Key, x.Value);
            }
            Console.Write("=> {0:#,0}円, {1}枚", Amount(), Count());
            Console.WriteLine();
        }

        public Wallet Pay(int payment) {
            if (this.Amount() < payment)
                return null;
            var save = this.Clone();
            int paid = 0;
            int workPayment = payment;
            foreach (var coinType in _coinTypes) {
                int nextType = NextCoinType(coinType);
                int currPayment = workPayment % nextType;
                if (PayPart(coinType, currPayment / coinType)) {
                    paid += currPayment;
                } else {
                    // 繰上げ処理
                    workPayment += nextType;
                }
                workPayment -= currPayment;
                if (paid >= payment)
                    break;
            }
            return save.Subtract(this);
        }


        public Wallet Subtract(Wallet b) {
            var work = new Wallet();
            foreach (var currency in _coinTypes)
                work.Coins[currency] = this.Coins[currency] - b.Coins[currency];
            return work;
        }

        public Wallet Add(Wallet b) {
            var work = new Wallet();
            foreach (var currency in _coinTypes)
                work.Coins[currency] = this.Coins[currency] + b.Coins[currency];
            return work;
        }

        public static Wallet Normalize(int amount) {
            var work = new Wallet();
            var workAmount = amount;
            foreach (var coinType in _coinTypes) {
                int nextType = NextCoinType(coinType);
                int amari = workAmount % nextType;
                work.Coins[coinType] = amari / coinType;
                workAmount -= amari;
            }
            return work;
        }

        private bool PayOneUnit(int payment, int currCoineType = 1) {
            if (payment == 0)
                return true;          // ぴったり払えた!
            var coins = _coinTypes.SkipWhile(x => x < currCoineType).TakeWhile(x => x <= payment);
            foreach (var coinType in coins) {
                if (payment % coinType != 0)
                    break;  // 絶対にぴったりの支払いは無理。無駄な探索を打ち切る
                if (Coins[coinType] > 0) {
                    Coins[coinType]--;
                    payment -= coinType;
                    bool r = PayOneUnit(payment, coinType);
                    if (r == true)
                        return true;
                    Coins[coinType]++;
                    payment += coinType;
                }
            }
            return false;
        }

        public bool PayPart(int coinType, int count) {
            var save = this.Clone();
            for (int i = 0; i < count; i++) {
                if (!PayOneUnit(coinType)) {
                    Coins = save.Coins;
                    return false;
                }
            }
            return true;
        }

        private Wallet Clone() {
            var obj = new Wallet();
            obj.Coins = new SortedDictionary<int, int>(this.Coins);
            return obj;
        }

        private static int GetIndex(int coinType) {
            return Array.FindIndex(_coinTypes, x => x == coinType);
        }

        private static int NextCoinType(int coinType) {
            int index = GetIndex(coinType) + 1;
            if (index < _coinTypes.Length)
                return _coinTypes[index];
            else
                return 100000;
        }
    }
}

なぜか今回は、である調で書いちゃいました。
である調にすると、なんだかいかにも偉そうだ(^^;;



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52412631