Javaの繰り返し文で複数の値を取得するには

Question

閲覧ありがとうございます。

javaの学習サイトで下記のような問題を発見したのですが導き方が全くわかりませんでした。

かなり考えて調べたのですが答えを導き出せなかったのでご教示いただきたいです・・・。

---

500円玉をA枚、100円玉をB枚、50円玉をC枚持っていたときに、
これらの硬貨の中から何枚かを選び、合計金額をちょうど X円にする
組み合わせを求める処理(関数)を作成してください。

条件/制約：
A,B,C,Xは全てintの引数。

実行例：
引数：2, 10, 3, 1100
結果：500円 2枚、100円 1枚、50円 0枚
500円 2枚、100円 0枚、50円 2枚
500円 1枚、100円 6枚、50円 0枚
500円 1枚、100円 5枚、50円 2枚
500円 0枚、100円 10枚、50円 2枚

---

for文でループさせる、ということはさすがにわかるのですが複数の値を取得し、
さらにそれを全パターン取るとなると正直お手上げでした。

このような関数を作成し、1パターンは取得できたもののここから進めませんでした。

お手数をおかけしますがどなたか教えていただきたいです。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        coinCheck(2, 9, 20, 900);
    }

        public static void coinCheck(int coin500,int coin100,int coin50,int total){
            int count500 = 0; //各コインの枚数
            int count100 = 0;
            int count50  = 0;
            
                for(int i = 0;(i <= coin500) && total >=500;i++){
                        count500++;
                        total -= 500;
                }

                for(int i = 1;(i <= coin100) && total>=100;i++){
                        count100++;
                        total -= 100;
                }
            
                for(int i = 1;(i <= coin50) && total >=50;i++){
                        count50++;
                        total -= 50;
                }

            if(total == 0 ){
                System.out.println("500円玉："+count500);
                System.out.println("100円玉："+count100);
                System.out.println("50円玉："+count50);
                System.out.println(total);
            }
        }
        
}

Answer 1

いまいちですが、とりあえず仕様は満たしているかと。。

package com.example;

public class Main {
	public static void main(String[] args) {
		coinCheck(2, 10, 3, 1100);
	}

	public static void coinCheck(int coin500, int coin100, int coin50, int total) {
		int max500 = Math.min(coin500, (total / 500));
		for (int i = max500; i >= 0; i--) {
			int balance = total;
			balance -= (i * 500);
			if (balance == 0) {
				resultOut(i, 0, 0);
				continue;
			}
			int max100 = Math.min(coin100, (balance / 100));
			for (int j = max100; j >= 0; j--) {
				int balanceAfter500 = balance;
				balanceAfter500 -= (j * 100);
				if (balanceAfter500 == 0) {
					resultOut(i, j, 0);
					continue;
				}
				int max50 = Math.min(coin50, (balanceAfter500 / 50));
				for (int k = max50; k >= 0; k--) {
					int balanceAfter100 = balanceAfter500;
					balanceAfter100 -= (k * 50);
					if (balanceAfter100 == 0) {
						resultOut(i, j, k);
						continue;
					}
				}
			}
		}
	}

	public static void resultOut(int count500, int count100, int count50) {
		System.out.print("500円玉" + count500 + "枚、");
		System.out.print("100円玉" + count100 + "枚、");
		System.out.println("50円玉" + count50 + "枚");
	}
}

Answer 2

2つの方法を書いてみました。2 番目はすこし計算量がすくないはずです。
もっと汎用的なメソッドにしたり、再帰をつかう方法も考えてみると良いです。

package teratail;

import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		show_result(coinCheck1(2, 10, 3, 1100));
		show_result(coinCheck2(2, 10, 3, 1100));
	}

	private static void show_result(List<Integer[]> ans) {
		for (Integer[] x : ans) {
			System.out.println("500円 " + x[0] + "枚、100円 " + x[1] + "枚、50円 " + x[2] + "枚");
		}
		System.out.println();
	}

	private static List<Integer[]> coinCheck1(int coin500, int coin100, int coin50, int total) {
		List<Integer[]> ans = new ArrayList<Integer[]>();

		for (int i = 0; i <= coin500; i++) {
			for (int j = 0; j <= coin100; j++) {
				for (int k = 0; k <= coin50; k++) {
					if (total == i * 500 + j * 100 + k * 50) {
						Integer[] x = { i, j, k };
						ans.add(x);
					}
				}
			}
		}
		return ans;
	}

	public static List<Integer[]> coinCheck2(int coin500, int coin100, int coin50, int total) {
		List<Integer[]> ans = new ArrayList<Integer[]>();

		for (int i = 0; i <= coin50; i++) {
			int sum50 = 50 + i;
			if (sum50 > total) {
				continue;
			}

			for (int j = 0; j <= coin100; j++) {
				int sum100 = 100 + i;
				if (sum50 + sum100 > total) {
					continue;
				}

				for (int k = 0; k <= coin500; k++) {
					if (total == i * 500 + j * 100 + k * 50) {
						Integer[] x = { i, j, k };
						ans.add(x);
					}
				}
			}
		}
		return ans;
	}
}

実行例：

Comments

[tmp-user]

ありがとうございます。
今回やりたかったことに最も近かったのでベストアンサーとさせていただきました。

for文中にfor文を入れることで全パターン網羅し、その後に必要なケースのみ
取得するというやり方が思いつかなかったので非常にスッキリしました。

ありがとうございました。

[katoy]

はい。 for を nest させて 組み合わせを列挙しています。
次の記事も参照してみてください。(python3 組み合わせ 列挙 で google 検索した)
https://qiita.com/junkls/items/10384950963056cc8e08

興味があれば、ぜひ再帰的な方法も挑戦してみてください。

Answer 3

ループのさせ方があまり良くないです。

例えば1100円の場合、使える500円玉は2枚以下、つまり
2枚、1枚、0枚のいずれかです。
このそれぞれに対して残り必要な金額を出し、それを支払うために必要な100円玉の枚数の候補をあげます。もちろん、ストックにある枚数以内で。
そうなると、残り金額を50円玉で支払う場合の枚数が自ずと決まるはずです。

これを全網羅していきます。