[동적 기획] 최소 동전 문제

최소 동전 문제
http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/3016/pid/1725
Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description
n 가지 서로 다른 액면가 의 동전 이 설치 되 어 있 고 각 동전 의 액면가 가 배열 T [1: n] 에 저 장 됩 니 다.지금 이 액면가 의 동전 으로 거스름돈 을 찾 으 려 고 합 니 다.사용 가능 한 각종 액면가 의 동전 개 수 는 배열 Coins [1: n] 에 저 장 됩 니 다.
임의의 금액 0 ≤ m ≤ 20001 에 대해 최소 동전 으로 m 를 찾 는 방법 을 설계 합 니 다.
주어진 1 ≤ n ≤ 10, 동전 액면가 수조 T 와 사용 가능 한 각종 액면가 의 동전 개수 수조 Coins, 그리고 돈 수 m, 0 ≤ m ≤ 20001, 거스름돈 m 의 최소 동전 수 를 계산한다.
Input
입력 데이터 의 첫 번 째 줄 에는 1 개의 정수 만 n 의 값 을 주 고 두 번 째 줄 부터 각각 T [j] 와 Coins [j] 이다.마지막 한 줄 은 거스름돈 m 입 니 다.
Output
출력 데 이 터 는 하나의 정수 만 있 고 계 산 된 최소 동전 수 를 나타 낸다.문제 가 풀 리 지 않 을 때 출력 - 1.
Sample Input

Sample Output

Hint

Source
알고리즘 사고방식:

이 문 제 는 '동적 계획' 알고리즘 을 사용 하여 큰 문 제 를 작은 문제 로 바 꾸 고 한 걸음 한 걸음 지난 결 과 를 기록한다.

우 리 는 계산 결 과 를 1 차원 배열 로 저장 하고 예전 의 '가방 문제' 알고리즘 을 참고 하여 해석 할 수 있 습 니 다.https://www.cnblogs.com/onetrainee/p/11672203.html

'가방 문제' 와 의 비교 와 분석:

'가방' 에서 '손실' 과 '수익' 을 제 시 했 지만 모두 하나의 물품 에 대해 최대 수익 을 구 했다.'동전' 에서 제시 한 것 은 '수익', '개수' 와 '최종 수익' 으로 최소 조합 을 구한다.

이 를 통 해 알 수 있 듯 이 '동전 문제' 에 대해 동태 적 인 계획 을 사용 하려 면 '한 걸음 한 걸음 걷 는 원칙' 에 따라 적어도 5 개 2 를 나 누 어야 한다. 예 를 들 어 5 개, 5 로 나 누 어 첫 번 째 5 를 계산 한 다음 에 두 번 째 5 를 계산 해 야 한다.

알고리즘 설계:

여전히 1 차원 배열 인 'dp [목표 면 액] = 최소 수요 개수' 로 최종 결 과 를 저장 합 니 다.

우 리 는 모든 동전 을 순서대로 한 개 로 나 누 었 다. dp [목표 면 액] = min (dp [목표 면 액 - 현재 면 액] + 1, dp [목표 면 액]). 앞의 하 나 는 이 면 액 을 이 조합 에 넣 었 고, 뒤의 하 나 는 현재 면 액 을 사용 하지 않 고 수치 가 가장 작은 것 을 선택 했다.

알고리즘 주의사항:

앞의 두 층 순환 은 면 액 을 나 누 어 경계 에 등호 가 있 는 지 주의 하 는 것 이다.

dp [k] 배열 이 초기 화 되 었 을 때 k = 0 을 제외 한 모든 수 치 는 무한대 로 설정 되 었 습 니 다. 수요 가 0 일 때 조합 수 는 원래 0 가지 이 고 이것 도 무한대 로 설정 하면 계산 할 수 없 기 때 문 입 니 다.

원본 코드:

 1 //   .cpp :       "main"   。             。
 2 //
 3 
 4 #include "pch.h"
 5 #include 
 6 #include 
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 
10 int main() {
11 
12     int des, n, T[20001], Coin[20001]; 
13     long long int dp[20001];
14     memset(dp, INF, sizeof(dp));
15     cin >> n;
16     for (int i = 0; i < n; i++) {
17         cin >> T[i] >> Coin[i];
18     }
19 
20     cin >> des;
21     dp[0] = 0;
22 
23     //            
24     for (int i = 0; i < n; i++)
25         for (int j = 1; j <= Coin[i]; j++)
26             for (int k = des; k >= T[i]; k--)
27                 dp[k] = min(dp[k], dp[k - T[i]] + 1); 
28 
29     cout << (dp[des]1) << endl;
30 }
31

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[동적 기획] 최소 동전 문제

좋은 웹페이지 즐겨찾기