백준 12865번 평범한 배낭 (C++)

 전형적인 DP memoization 문제이다.

배낭 문제는 NP-hard 문제로 그리디 알고리즘으로 해결할 수 없음이 증명되어있다.

그러므로 주어진 N번만큼을 메모이제이션을 통해 DP 행렬을 갱신해가며 최적의 답을 구하는 수 밖에 없다.

메모이제이션 결과

 주어진 예를 들었을 경우다. 

6 13 이 들어오면 처음이니 그냥 써주고

4 8이 들어오면 이전과 비교해서 갱신해준다.

이때 DP[2][4] 는 이전이 0이었는데 8로 바뀌었다. 

-> DP[2][4] = max(DP[1][4], DP[1][0] + 8)

 

그러므로 점화식을 구하면 DP[i][j] = max(DP[i - 1][j - w] + value, DP[i -1][j])

 

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

struct bag {
	int w;
	int v;
};
int DP[101][100001] = { 0, };
bag Data[101];

int main() {
	int n, w;
	int answer = 0;
	
	cin >> n >> w;

	for (int i = 1; i <= n; i++) {
		cin >> Data[i].w >> Data[i].v;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= w; j++) {
			if (j >= Data[i].w)
				DP[i][j] = max(DP[i - 1][j - Data[i].w] + Data[i].v, DP[i - 1][j]);
			else
				DP[i][j] = DP[i - 1][j];
		
		answer = max(answer, DP[i][j]);
		}
	}

	cout << answer;
}

 

범위 잘못잡았다.