Java:コイン交換(発色アルゴリズム)

7570 ワード
テキストリンク

質問する



に答える


  • 時間的複雑さを考慮して,dfsで解決した問題を完全探索することを試みた.

  • 硬貨の数と硬貨の配列を格納するためにdp配列dyを作成する.

  • j 1番目の硬貨の個数dy[j]は、j元を取り戻すために用いられる硬貨の最小個数である.

  • コインによっては、探しているコインの個数を計算し、dyを格納します.

    • おしゃべり

  • dpアルゴリズムの一種で、暗色とはリュックサックと宝石が限られた空間(バッグの大きさ)に最大価値のある宝石を入れることを指す.(リュック=リュック)

    • 完全なコード

    package inflearn;

import java.util.Scanner;

public class I1005 {

	static int n;
	static int m;
	static int[] dy;
	static int[] coinArr;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		coinArr = new int[n];

		for (int i = 0; i < n; i++) {
			coinArr[i] = sc.nextInt();
		}

		m = sc.nextInt();
		dy = new int[m + 1];
		for (int i = 1; i < dy.length; i++) {
			dy[i] = Integer.MAX_VALUE;
		}

		System.out.println(knapsack());
	}

	static int knapsack() {
		for (int coin : coinArr) {
			for (int j = coin; j <= m; j++) {
				int tmp = dy[j - coin] + 1;
				if (dy[j] > tmp) dy[j] = tmp;
			}
		}
		return dy[m];
	}
}
    nested relations
    白駿解答-ブラックジャック2798号