백준 12865

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

이 문제는 내가 지금 까지 DP배열을 1차원 배열로 만드는데 익숙 해져서 그런지 2차원 배열로 설정 하는 것을 생각을 못해서 어려운 문제 였다. 이 문제의 경우 나는 이렇게 생각 해주었다.

일단 나는 이문제를 1번 아이템 부터 4번아이템을 넣어준다고 가졍하였다 이문제에서 0은 어떠한 아이템도 안 넣었다고 생각해서 0이자 무게가 0이라고 생각을 했다 이렇게 생각하지 않으면 너무 헷갈렸다 그래서 1번을 넣었을 때 무게가 6이고 7인 경우에는 1을 넣었기 때문에 1의 무게인 13을 넣었다. 1을 넣었을 때 무게가 1,2,3,4 일 수는 없으니 1을 넣지 않았다는 표시이자 안 넣었고 무게도 0이니 0으로 한다. 2번아이템을 넣었을 때 도 마찬가지 무게가 1,2,일 때는 2번을 넣었을 때

무게가 4로 초과되니 0으로 표시한다 그후 무게가 4랑 5일때는 

나의 이전 단계인 1을 넣었을 때의 무게들 중 나를 안넣었다고 가정한 무게 + 나의 무게를 했을 때와 이전단계의 무게들과 비교하여 더큰 값을 넣어준다. 이것을  dp로 표현 하면

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); 

예시로 dp[2][6]은 dp[1][2]+v[2] 과 dp[1][6]일 때를 비교한다 이 의미는 1을 먼저 넣을 안넣을 지 결정하는 상태에서 무게가 2일때+나의 더했을 때의 가치와 1을 넣을 안넣을지 결정했을 무게가 6인 경우를 비교하여 더 큰 값을 선택한다.

쉽게 설명하자면

1을 넣을지 말지 결정했을 때  특정 무게를 맞춘다고 가정했을 때 나의 무게를 더해서 그 무게를 맞춘다고 가정한 값과 이전 단계에서 그 무게를 달성했을 때의 값을 비교하여 큰값을 선택해 주는것이다.

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[101][100001];//가방 물건의 번호,내가방의 무게
int W[101];
int V[101];
int main() {
	int maxItemNum;
	int maxItemWeight;
	cin >> maxItemNum >> maxItemWeight;

	for(int i=1; i<=maxItemNum; i++){
		cin >> W[i] >> V[i];
	}

	for (int i = 1; i <= maxItemNum; i++) {
		for (int j = 1; j <= maxItemWeight; j++) {
			if (j - W[i]>=0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[maxItemNum][maxItemWeight];
}

그래서 이러한 점화식으로 이문제를 풀면 전체 식이 이렇게 된다. 1차원으로 dp를 세우는 거 뿐만 아니라 다차원의dp 도 세우는 방법을 연습해야 할거 같다.