C(c1, c2, …Cn) 코인 목록이 있으며 V 값도 제공됩니다. 이제 문제는 최소한의 코인을 사용하여 기회를 V로 만드는 것입니다.
참고: 무한한 수의 동전 C가 있다고 가정합니다.
이 문제에서는 C{1, 2, 5, 10}가 주어진 서로 다른 동전 세트를 고려할 것입니다. 각 유형의 동전 수는 무한합니다. 요청한 값을 변경하기 위해 모든 유형의 최소 동전 수를 사용하려고 합니다. 예를 들어 값이 22인 경우 {10, 10, 2}, 3개의 동전을 최소값으로 선택합니다.
입력 및 출력
Input: The required value. Say 48 Output: Minimum required coins. Here the output is 7. 48 = 10 + 10 + 10 + 10 + 5 + 2 + 1
알고리즘
minCoins(coinList, n, value)
입력: 다양한 코인 목록, 코인 수, 주어진 가치
출력: 주어진 가치를 얻기 위한 최소 코인 수입니다.
Begin if value = 0, then return 0 define coins array of size value + 1, fill with ∞ coins[0] := 0 for i := 1 to value, do for j := 0 to n, do if coinList[j] <= i, then tempCoins := coins[i-coinList[j]] if tempCoins ≠ ∞ and (tempCoins + 1) < coins[i], then coins[i] := tempCoins + 1 done done return coins[value] End
예시
#include<iostream> using namespace std; int minCoins(int coinList[], int n, int value) { int coins[value+1]; //store minimum coins for value i if(value == 0) return 0; //for value 0, it needs 0 coin coins[0] = 0; for (int i=1; i<=value; i++) coins[i] = INT_MAX; //initially all values are infinity except 0 value for (int i=1; i<=value; i++) { //for all values 1 to value, find minimum values for (int j=0; j<n; j++) if (coinList[j] <= i) { int tempCoins = coins[i-coinList[j]]; if (tempCoins != INT_MAX && tempCoins + 1 < coins[i]) coins[i] = tempCoins + 1; } } return coins[value]; //number of coins for value } int main() { int coins[] = {1, 2, 5, 10}; int n = 4, value; cout << "Enter Value: "; cin >> value; cout << "Minimum "<<minCoins(coins, n, value)<<" coins required."; return 0; }
출력
Enter Value: 48 Minimum 7 coins required.