3桁の金種計算で最小の支払い枚数を求めるプログラム

Question

3桁（1円～999円）までの支払いで、硬貨の最小の枚数を求めるプログラムを作成しています。
考え方としては、下記のようにしようと思っています。

１円硬貨を使わない場合、
１円と５円硬貨を使わない場合、
１円と５円と１０円硬貨を使わない場合、
１円と５円と１０円と５０円硬貨を使わない場合、
１円と５円と１０円と５０円と１００円硬貨を使わない場合、
全ての硬貨を使う場合。

うまくいく時といかないときがあり、その違いがわかりません。
お教えいただけたら、幸いです。
javaを勉強し始めて、2週間ほどなのでわかりやすくお教えいただけたら助かります。
よろしくお願いいたします。

import java.util.*;

public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int price = sc.nextInt();
int price_1,price_2,change,upper_price;

    int[] type = {500, 100, 50, 10, 5, 1};
    int[] count = { 0, 0, 0, 0, 0, 0 };
    int min = 0;//お釣りの最小枚数を入れる（最初はパターン１の値を入れて比べていく）
    int total_count = 0;//使用硬貨の合計枚数
    int len = len = type.length - 1;
    
    int total_change_count = 0;//お釣りの硬貨枚数
    int[] change_count = { 0, 0, 0, 0, 0, 0 };//お釣りの硬貨枚数用
    
    price_1 = price;//お釣りのないパターン
  
    for(int i = 0; i < type.length;i++){
        count[i] = price_1 / type[i];
        price_1 %= type[i];
        total_count += count[i];
    }
    min = total_count;//minをお釣りのない硬貨の枚数で初期化
   
  //お釣りありのパターン
    for(int i = 1; i < type.length; i++){
        price_2 = price % type[len - i];//入力値を5で割った余り
        change =  type[len - i] - price_2;//5-↑の余り値
        upper_price = price + change;//お釣り込みの値段＝1の位が0
        total_count = 0;//total_countは何度も使うので0に初期化
        total_change_count = 0;//total_change_countは何度も使うので0に初期化

        System.out.println("change = " + change);

       //お釣りの硬貨枚数計算
        for(int k = 0 ;k < type.length;k++){
            
            change_count[k] = change / type[k];
            change %= type[k];
            total_change_count += change_count[k];
        }
        System.out.println("total_change_count = " + total_change_count);
        
        
        for(int j = 0; j < (type.length - i); j++){
            count[j] = upper_price / type[j];
            upper_price %= type[j];
            total_count += count[j];
        }
        total_count += total_change_count; 
        System.out.println("totalCount = " + total_count);
        
        if(min > total_count){
        min = total_count;
        }
    }
    System.out.println(min);

}
}

Comments

[swordone]

「うまく行かない時」の具体的な事象を掲載してください。

[Daregada]

要件が明確に定義されていないように思います。
「最小の支払い枚数」だけでいいのなら毎回500円玉だけ1～2枚出していればいいのでは。
「硬貨の最小の枚数」とは、「支払いに使った硬貨の枚数 + 理想的な最小枚数で返ってくるお釣りの硬貨の枚数」なんですかね。

[退会済みユーザー]

何度かこの手のはあったきがする

お釣りの計算アルゴリズム

[kinako_make]

そうですね。
支払いとおつりを合わせた硬貨の枚数が最小限になるプログラムです。
しっかりと定義出来ていなくて、申し訳ございません。
支払いに使用できる硬貨の枚数に制限はありません。

[kinako_make]

おつりの計算のプログラムは見つけたのですが
使用できる硬貨に制限がないパターンのは見つからず、どう考えるのがいいのかわからなかったのでお聞きしました。

[momon-ga]

意外に面倒ですね・・・
おつりが０枚になる払い方が必ず最小というわけではないっていうのがポイントか。
14円の場合、10円と4円でおつり無し(合計5枚)より10円5円の2枚とおつり１枚の３枚が最小になるのね。
っていう端数のおつりで、どちらが小さくなるかを求めるようなロジックになりそう

[kinako_make]

そうなんですよ…
このプログラムコードでは、146円の場合6枚と表示されますが、最小枚数は4枚（151円とお釣り1円）になるのでもう少し考える必要があるのはわかります。
ただ、どこが間違ってるのか、
もしくは足らないだけなのかがわからず深みにはまってます。

[momon-ga]

ロジック見てないけど、４円、４０円、４００円の時だけ回避用のロジック仕込めばいいんじゃ？
(5円、50円、500円を使っておつりをもらったほうが少ないケース)

[kinako_make]

私のやり方が悪かったようで、146円のような場合ができるようになったら、次は通常のできてた金額ができまくなってしまいました。（128円は最小6枚なのに、4枚になってしまいました。）
硬貨の枚数が1の位と5の位が合わせて4なら10の位に上がるようにしたんですが、なかなかうまくいってないようで一つずつ表示して確認しています…

Answer 1

コードをそのままだとためにならないので設計だけ。

1. お釣りの最小枚数を計算するロジックを作成する。
2. 500円がある場合お釣りのストックが足りているか？
3. もし不足していたら100円玉の使用枚数に＋５する
4. 100円がある場合お釣りのストックが足りているか？
5. もし不足していたら50円玉の使用枚数に＋２する
6. 50円がある場合お釣りのストックが足りているか？
7. もし不足していたら10円玉の使用枚数に＋５する
8. 10円がある場合お釣りのストックが足りているか？
9. もし不足していたら5円玉の使用枚数に＋２する
10. 5円がある場合お釣りのストックが足りているか？
11. もし不足していたら1円玉の使用枚数に＋５する
12. 1円がある場合お釣りのストックが足りているか？
13. もし不足していたらエラーとする
14. 返却枚数が 規定(突飛な話、１円玉 500枚をお釣りと渡したら怒りますよね） を超え場合もエラー（もしくは警告）とする

Comments

[kinako_make]

ありがとうございます！
考えてみます。

Answer 2

支払金額

金額の下の桁から順に各桁で以下を繰返す。

• 数の5の剰余が3以上の場合、その数の[5の補数]を加算する(5か10に丸める)
• 加算結果が10に丸められたら、繰り上がりを行う

枚数

• 上の計算結果が支払う金額である。貨幣の枚数は各桁の[n/5 + n%5]の合計
  ただし1000のときは+1枚する（500円硬化2枚）
• お釣りの枚数は上の[5の補数]の合計

まだ未確認です。問題があれば指摘してください。

支払方法

1000円を超える支払を許すことになります。例えば、996円に対して1006円を支払うなど。

根拠

釣り銭ありと、釣り銭なしの、枚数を確認してください。

ダメな根拠

お釣り１円１０円だけで、５円５０円が発生する場合が考慮されていません。
５円５０円のパターンがどこに出るかを発見すれば、課題解決するでしょう。

• 45,46,47 (95, 96, 97は同じパターンか？）
• 450,460,470 (950, 960, 970は同じパターンか？）

お釣りの枚数計算は補数ではなくなります。少し見通しが良くなりました。

ルール追加

上の支払い金額ルールに次のルールを追加します。

• 数の5の剰余が3未満の場合

　数に5を足して繰り上がる場合、繰り上げ後の次の桁が5か10になる (なら枚数が減るだろう)
・5を足して繰り上げ処理を行う。
・お釣りの枚数+1

問題はすでに解けているのではないかと思います。備忘録として追記します。
不具合を発見すればその都度ルールを見直してください。

Comments

[kinako_make]

ありがとうございます！
考えてみます。

[kinako_make]

やってみました。128円は最小枚数6枚でOKでした！
でも368円は最小7枚ですが、8枚。146円は最小枚数4枚ですが、7枚でした。
私の理解度がなく間違ってるところがあれば、ご指摘お願いいたします。

import java.util.*;

public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
String str_price = sc.next();
int[] price = new int[str_price.length()];

for(int i = 0;i < str_price.length(); i++) {
price[i] = Integer.parseInt(str_price.substring(i, i+1));
System.out.println(price[i] + " i = " + i);
}

int total_count = 0;
int add = 0;
int count = 0;
int hosu = 0;
int rem = 0;

//支払い金額を求める
for(int i = 2;i >= 0;i--){
rem = price[i] % 5;
if(rem >= 3){
if(price[i] >= 5){
hosu = 10 - price[i];
add = price[i] + hosu;
}
// else{
// change = price[i] + (5 - price[i]);
// }
if(add == 10){
count += hosu;
price[i - 1] += 1;
price[i] = 0;
}
}else{
break;
}
};

//硬貨の支払い枚数を求める
for(int i = 0; i < str_price.length(); i++){
total_count += (price[i] / 5) + (price[i] % 5);

}
total_count += change_count;
System.out.println("total_count = " + total_count);

}
}

[xebme]

・桁繰り上がりがあるので配列の要素数は4。要素番号0は繰り上がり用。
・繰り上がりは隣の桁だけでなくさらに上の桁まで考慮。999の時を考えてください。
・お釣りの枚数は、change_count += hosu;
・最上位桁に1が繰り上がっていれば500円が2枚になるので+1枚