Coin Exchange

11 Aug, 2021

Problem

How can I exchange change for the smallest number of coins when several units of coins are given as follows? Each unit of coins can be used indefinitely.

input

In the first line, the number of types of coins N (1<=N<=12) is given. The second line is given N types of coins, and the next line is given the amount M (1<=M<=500) to be reversed
Each type of coin does not exceed 100 won

output

Prints the minimum number of coins in the first line.

3;

// Description: Can be given back with 3 5 5 5 coins.

Solution

function solution(m, arr) {
	let answer = Number.MAX_SAFE_INTEGER;

	function DFS(l, sum) {
		if (sum > m) return;
		if (sum === m) {
			if (answer > l) answer = l;
		} else {
			for (let i = 0; i < arr.length; i++) DFS(l + 1, sum + arr[i]);
		}
	}

	DFS(0, 0);

	return answer;
}

function solution(m, arr) {
	let answer = Number.MAX_SAFE_INTEGER;
	let n = arr.length;

	function DFS(L, sum) {
		if (sum > m) return;
		if (L >= answer) return; // performance optimized

		if (sum === m) {
			answer = Math.min(answer, L);
		} else {
			for (let i = 0; i < n; i++) DFS(L + 1, sum + arr[i]);
		}
	}

	DFS(0, 0);

	return answer;
}