동전 거스름돈 문제 (동적 계획)

1. 제목 설명
    거스름돈 이 필요 한 액면가 money 와 사용 할 수 있 는 동전 의 종 류 를 정 합 니 다.예 를 들 어 머 니 = 7, 동전 의 종 류 는 [1, 2, 5] 이 므 로 액면가 2 의 동전 1 개 와 5 의 동전 1 개 를 거 슬러 야 하 며 총 동전 수 는 2 개 이다.
2. 문제 풀이 사고
   동적 계획 을 사용 하여 설명: 우 리 는 d (i) = j 로 i 원 을 모 으 려 면 최소 j 개의 동전 이 필요 하 다 는 것 을 표시 합 니 다.그래서 우 리 는 이미 d (0) = 0 을 얻 었 고 0 원 을 모 으 려 면 최소 0 개의 동전 이 필요 하 다 는 뜻 이다.i = 1 시 액면가 가 1 인 동전 만 사용 할 수 있 기 때문에:
    d(1) = d(1-1) + 1 = d(0) + 1 = 0 + 1 = 1；
i = 2 시, 이때 사용 할 수 있 는 동전 은 1 과 2 입 니 다. 그러면 우 리 는 어느 것 을 사용 합 니까?우리 가 선택 한 이 동전 이 동전 수 를 최소 화 할 수 있 도록 확보 해 야 하기 때문에 우리 의 선택 은:
    d（2）= min{ d( 2 - 2) + 1，d（2 -1）+ 1} = min{ d（0）+1，d（1）+1 } = 1；
i = 3 시 사용 가능 한 동전 은 1 과 2 입 니 다. 우리 의 선택 은:
    d（3）= min{ d( 3 - 2) + 1，d（3 -1）+ 1} = min{ d（1）+1，d（2）+1 } = 2；
i = 4 시 사용 가능 한 동전 은 1 과 2 입 니 다. 우리 의 선택 은:
    d（4）= min{ d(4 - 2) + 1，d（4 -1）+ 1} = min{ d（2）+1，d（3）+1 } = 2；
당 i = 5 사용 가능 한 동전 은 1, 2, 5 입 니 다. 우리 의 선택 은:
    d（5）= min{ d(5 - 5) + 1，d(5 - 2) + 1，d（5 -1）+ 1} = min{ d（0）+1，d（3）+1，d（4）+1 } = 1。
코드 는 다음 과 같 습 니 다:

#include
#include
#include
#include
using namespace std;

int main() {
	int money = 63;
	vector coin({ 1,2,5,21,25 });
	sort(coin.begin(), coin.end());
	vector status;
	for (int i = 0; i <= money; i++)
		status.push_back(0);

	for (int i = 1; i <= money; i++) {		
		int min = INT_MAX;
		int j = 0;
		while (j= 0) {
			min = min >(status[i - coin[j]]) ? (status[i - coin[j]] + 1) : min;
			j++;
		}		
		status[i] = min;
	}

	for (int i = 0; i < status.size(); i++)
		cout << status[i] << " ";
	cout << endl;
	if (status[money] == 0)
		cout << "can not find" << endl;
	else
		cout << status[money]<

    주의: 실제 상황 에서 찾 을 수 없 는 상황 이 있 을 수 있 으 므 로 d (0) 를 제외 하고 다른 상황 에서 d (i) = 0 은 이러한 액면가 의 잔돈 을 찾 을 수 없 음 을 나타 내 므 로 사용 할 때 이 점 을 고려 해 야 합 니 다.