DP(동적 계획법)의 노하우

막 경기 프로그램 설계를 시작했는데 사회에서'개미본'이라고 부르는 것을 참고하여 학습을 했는데 결과적으로 2-3장의 동태계획법에 부딪혔다.
처음에 동적 계획법을 읽을 때 DP 코드를 쓸 수 있을지는 말할 것도 없고 개념 자체도 잘 이해하지 못했지만 인터넷에서 많은 사이트를 참고하여 이해하고자 할 때 DP 문제를 스스로 해결하는'비결'을 찾았습니다!여기서 이 비결을 적어 보겠습니다. 가능하다면 저처럼 다른 DP를 공부하는 사람이 저처럼 잘 모르는 사람에게 도움이 되거나 장래의 저에게 노트가 되었으면 좋겠습니다.
그럼, 우리 빨리 보러 갑시다!
DP와 관련된 기고문 링크가 온라인에 업로드되었습니다.
-　 동적 계획법(가방 문제)
-　 자동 프로그래밍
※ 주의: 이곳의 노하우는 전형적인'가방 문제'와'동전 문제'등에만 적용됩니다.복잡한 DP 문제가 아직 처리되지 않았기 때문에...
프로그램을 작성할 때의 생각은 다음과 같다.
1. 복귀하는 전체 검색 프로그램 도입을 고려
2. 덮어쓸 수 있는 값에 dp 목록을 가져옵니다
3. (완성 후) 점화식 기반 프로그램 편성
이런 느낌이야.
그럼 예를 들어 봅시다.
문제: 보물이 많이 소장된 박물관에서 도둑이 큰 보자기를 들고 잠입했다.훔치고 싶은 물건이 많지만 보자기의 무게가 제한되어 이것을 초과하면 보자기가 터진다.따라서 도둑은 미리 준비한 보자기를 깨뜨리지 않고 가장 가치가 높은 보물 조합을 고려해야 한다.
*보따리 무게를 견딜 수 있는 W와 박물관에 있는 각 보물의 가치와 무게를 읽고 무게 합계가 W를 초과하지 않는 범위 내에서 가치 합계가 최대일 때 보물 가치 합계를 출력하는 프로그램을 만드세요.그러나 가치 총화의 가장 큰 조합이 여러 개 있을 때 수출 중량은 작은 것을 총화한다.
(W ≤ 1,000, 1 ≤ N ≤ 1,000)
(PCK 2004년 예비선거 문제의 개조)
이 질문을 다 검색하면...
zensousaku.cpp

#include <bits/stdc++.h>
using namespace std;

int n, w;
pair<int, int> takara[1050];

int solve(int w, int p){
int res;
if(p == n)res = 0;
else if(w < takara[p].second)res = solve(w, p+1);
else if(w >= takara[p].second)res = max(solve(w, p+1), solve(w-takara[p].second, p+1) + takara[p].first);
return res;
}

int main(){

scanf("%d", &w);
scanf("%d", &n);

for(int i = 0; i < n; i++)cin >> takara[i].first >> takara[i].second;

cout << solve(w, 0) << endl;
}

.
동적 계획법을 채택한다면
dp.cpp

#include <bits/stdc++.h>
using namespace std;

int n, w;
int dp[1050][1050];
pair<int, int> takara[1050];

int solve(int w, int p){
int res;
if(dp[w][p] != -1)return dp[w][p];
if(p == n)res = 0;
else if(w < takara[p].second)res = solve(w, p+1);
else if(w >= takara[p].second)res = max(solve(w, p+1), solve(w-takara[p].second, p+1) + takara[p].first);
return dp[w][p] = res;
}

int main(){

scanf("%d", &w);
scanf("%d", &n);

for(int i = 0; i < n; i++)cin >> takara[i].first >> takara[i].second;

memset(dp, -1, sizeof(dp));

cout << solve(w, 0) << endl << ;
}

.zensousaku.cpp와 dp.cpp를 비교하면 dp의 목록을 사용했는지, 그리고 함수가 이미 계산한 값을 요구하면 계산한 값if(dp[w][p] != -1)return dp[w][p];만 되돌려줄 수 있음을 알 수 있다.
이렇게 하면 전체 검색에서 코드를 간단하게 DP로 변환할 수 있다.
참고할 가치가 있습니까?투고의 문제점과 오류 등이 발견되면 마음대로 메시지를 남겨주세요!