DP_동전 문제

동적 계획 알고리즘 은 보통 하나의 전달 공식 과 하나 이상 의 초기 상 태 를 바탕 으로 한다.현재 하위 문제 의 해 는 지난번 하위 문제 의 해 에서 나 올 것 이다.동적 계획 을 사용 하여 문 제 를 풀 려 면 여러 가지 시간 복잡 도 만 필요 하기 때문에 역 추적 법, 폭력 법 등 보다 훨씬 빠르다.동적 계획 도 면접 필기시험 문제 의 한 시험 중점 이다. 한 문 제 를 읽 고 해결 하려 고 할 때 먼저 그 제한 을 살 펴 보 자.여러 시간 안에 해결 하 라 고 요구 하면 이 문 제 는 DP 로 풀 어야 할 가능성 이 크다.이런 상황 에 부 딪 히 면 가장 중요 한 것 은 문제 의 '상태' 와 '상태 전이 방정식' 을 찾 는 것 이다.(상 태 는 마음대로 정 의 된 것 이 아 닙 니 다. 일반적으로 상 태 를 정의 합 니 다. 현재 상태 가 앞의 상태 에서 어떻게 얻 는 지, 즉 상태 이동 방정식 을 찾 아야 합 니 다) DP 문제 로 보이 지만 상 태 를 정의 할 수 없다 면 문 제 를 이미 알 고 있 는 DP 문제 로 규정 해 보 세 요.
여기 서 먼저 가장 간단 한 동적 계획 인 스 턴 스 를 설명 한다. 동전 문제.다음 에 더 많은 인 스 턴 스 를 제공 할 것 입 니 다. 예 를 들 어 가장 긴 공공 서브 시퀀스, 가장 긴 공공 서브 문자열, 가장 긴 서브 시퀀스, 문자열 편집 거리 등 입 니 다.동적 계획 의 관건 은 '상태' 와 '상태 전이 방정식' 을 찾 는 것 이다.
동전 문제: 액면가 의 동전 을 드 리 고 N 값 을 드 리 겠 습 니 다. N 을 구성 하 는 데 필요 한 최소 동전 의 수량 과 방안 을 구 해 달라 고 합 니 다.분석: 이 문 제 는 욕심 산법 으로 해결 해 볼 수 있 습 니 다. 먼저 액면가 가 가장 큰 동전 부터 시도 하고 계속 찾 아 보 세 요. 동전 의 총 화 는 N 이라는 것 을 알 고 있 습 니 다.그러나 욕심 산법 은 해 를 찾 을 수 있다 고 장담 할 수 없다 (예 를 들 어 2, 3, 5, 그리고 N = 11).우 리 는 생각 을 바 꿀 수 있다. 우 리 는 d (i) 로 i 의 최소 동전 수량 (사실은 동적 계획 중의 '상태') 을 나타 낸다. 그러면 어떻게 앞의 상태 (반드시 d (i - 1) 라 는 상태 가 아니 라 d (i) 라 는 상태 까지?동전 집합 이 coins [0 ~ N] 이 라 고 가정 하면 d (i) 를 구하 기 전에 우 리 는 d (1 ~ i - 1) 를 모두 구 했다 고 가정 하면 d (i) = min {d (j) + 1}, if i - j 는 coins 에서 (사실은 이것 이 '상태 전이 방정식') 이다.달리 우 리 는 모든 액면 가 를 하나의 점 으로 본다!충분 한 액면가 가 필요 하 다 는 뜻 으로 초기 상 태 는 S, 목표 상 태 는 0 이다.그러면 현재 상태 가 i 이면 동전 j 를 사용 할 때마다 상태 가 i - Vj 로 전 이 됩 니 다.
예 를 들 어 coins = {2, 3, 5}, N = 11.
d(0)=0;
d(1)=0;
d(2)=d(0)+1=1;
d(3)=d(0)+1=1;
d(4)=d(2)+1=2;
d(5)=min{d(3)+1,d(2)+1,d(0)+1}=1;
d(6)=min{d(4)+1,d(3)+1}=2;
.......................
또한 마지막 방안 (동전 개수 뿐만 아니 라) 을 구하 기 위해 서 는 각 상태 에서 선택 한 '경로' 를 기록 해 야 한다. 예 를 들 어 d (5) 를 구하 기 위해 우 리 는 d (0) + 1 을 선택 했다. 그러면 우리 가 선택 한 경 로 는 5 - 0 = 5 이다.우 리 는 이 경 로 를 기록 한 후에 경로 에 따라 결 과 를 얻어 야 한다.d (6) 에 대해 우 리 는 3 을 선택 하기 시작 했다. 즉, 우 리 는 d (3) 상태 와 동전 3 에서 d (6) 로 넘 어 가 는 것 을 선택 했다. 이 어 d (3) 에 대해 우 리 는 3 을 선택 했다. 즉, 우 리 는 d (0) 상태 와 동전 3 에서 d (3) 로 넘 어 가 는 것 을 선택 했다. 이 어 d (0) 에 대해 이것 은 초기 상태 이다.그 러 니까 우리 방안 은 3, 3.
푸 시 (최소 순서 인쇄): 

#include 
#include 

using namespace std;

const int MAXN = 10000;
const int INF = 1000000000;
int n, S, V[MAXN], minn[MAXN], maxn[MAXN];   
//minn[i]         i  ，          ！maxn[i]         i  ，          ！

void print_ans(int* d, int S) {
  for(int i = 1; i <= n; ++i) {
    if(S >= V[i] && d[S] == d[S - V[i]] + 1){	//              ！
      cout << i << " ";
      print_ans(d, S-V[i]);
      break;   //      ！
    }
  }
}

int main() {
  cin >> n >> S;
  for(int i = 1; i <= n; ++i) {
    cin >> V[i];
  }
  for(int i=1; i<=S; ++i){
  	minn[i]=INF;maxn[i]=-INF;
  }
   for(int i=1; i<=S; ++i)
  	printf("minn=%d
",minn[i]);
  	
  for(int i = 1; i <= S; ++i) {   //  ！    minn[1...S] maxn[1...S]！
    for(int j = 1; j <= n; ++j) {
      if(i >= V[j]) {
        minn[i] = min(minn[i], minn[i - V[j]] + 1);
        maxn[i] = max(maxn[i], maxn[i - V[j]] + 1);
      }
    }
  }
  cout << minn[S] << endl;
  cout << maxn[S] << endl;
  print_ans(minn, S);
  cout << endl;
  print_ans(maxn, S);
  cout << endl;
  return 0;
}

다른 인쇄 방식:

#include 
#include 
using namespace std;

const int MAXN = 10000;
const int INF = 1000000000;
int n, S, V[MAXN], minn[MAXN], maxn[MAXN];
//minn[i]         i  ，          ！maxn[i]         i  ，          ！
int min_coin[MAXN], max_coin[MAXN];  
//min_coin[S]      minn[S] = minn[S-V[i]]+1    i。

void print_ans(int* d, int S) {
  while(S) {
    cout << d[S] << " ";
    S -= V[d[S]];
  }
}

int main() {
  cin >> n >> S;
  for(int i = 1; i <= n; ++i) {
    cin >> V[i];
  }
  for(int i=1; i<=S; ++i){
  	minn[i]=INF;maxn[i]=-INF;
  }
  for(int i = 1; i <= S; ++i) {   //  ！    minn[1...S] maxn[1...S]！
    for(int j = 1; j <= n; ++j) {
      if(i >= V[j]) {
        if(minn[i] > minn[i - V[j]] + 1) {
          minn[i] = minn[i - V[j]] + 1;
          min_coin[i] = j;
        }
        if(maxn[i] < maxn[i - V[j]] + 1) {
          maxn[i] = maxn[i - V[j]] + 1;
          max_coin[i] = j;
        }
      }
    }
  }
  cout << minn[S] << endl;
  cout << maxn[S] << endl;
  print_ans(min_coin, S);
  cout << endl;
  print_ans(max_coin, S);
  cout << endl;
  return 0;
}