백준 12865 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

이번에 풀어본 문제는 대표적이라 하는(?) 냅색 문제이다.

냅색 문제는 가방에 무게와 가치가 주어졌을 때, 가방의 무게 안에 가장 큰 가치를 챙기게 하는 로직으로 가야한다.

그리디한 방식으로는 전부 반례가 있다.

 

#include <iostream>
using namespace std;

int n, k, ar[101][2], d[101][100001];

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> ar[i][0] >> ar[i][1];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < ar[i][0]) d[i][j] = d[i - 1][j];
			else d[i][j] = max(d[i - 1][j - ar[i][0]] + ar[i][1], d[i - 1][j]);
		}
	}
	//for (int i = 1; i <= n; i++) {
	//	for (int j = 0; j <= k; j++) {
	//		cout << d[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	cout << d[n][k] << endl;

	return 0;
}

 

바텀업으로 풀어봤다. 주목해야 할 코드는

		if (j < ar[i][0]) d[i][j] = d[i - 1][j];
		else d[i][j] = max(d[i - 1][j - ar[i][0]] + ar[i][1], d[i - 1][j]);

이 코드다. 

이중 포문으로 j를 하나씩 올려가면서 현재 가방의 무게보다 작다면, 그 윗 단계의 가방을 가져오고,

j가 현재 가방의 무게 이상이라면 이번 가방의 가치를 포함한 것과, 포함하지 않고 전 단계의 가방을 가져온 것의 합 중 

큰 것을 가져온다.

 

주석 처리한 코드로 살펴보면 어떤 식으로 진행되는지를 알 수 있다. 식은 간단하지만 이해하는데는 생각보다 오래 걸린다.

 

#include <iostream>
using namespace std;

int n, k, ar[101][2], d[101][100001];

int go(int i, int w) {
	if (i == n + 1) return 0;
	if (d[i][w]) return d[i][w];
	int n = 0, n2;
	if (w + ar[i][0] <= k) n = ar[i][1] + go(i + 1, w + ar[i][0]);
	n2 = go(i + 1, w);
	return d[i][w] = n > n2 ? n : n2;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> ar[i][0] >> ar[i][1];

	cout << go(1, 0) << endl;

	return 0;
}

 

이번에는 무게를 함수 인자로 넘겨줘서 메모이제이션을 해줬다.

	if (w + ar[i][0] <= k) n = ar[i][1] + go(i + 1, w + ar[i][0]);
	n2 = go(i + 1, w);
	return d[i][w] = n > n2 ? n : n2;

이번 물건의 무게를 포함한 무게가 버틸 수 있는 무게를 넘지 않았다면 넣어보고, 그냥 넣지 않고 스킵한 것중 큰 값을 

dp에 넣어서 리턴해준다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int d[100001], ar[101][2];

int main() {
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) cin >> ar[i][0] >> ar[i][1];

	for (int i = 0; i < n; i++) {
		for (int j = k - ar[i][0]; j >= 0; j--) {
			d[j + ar[i][0]] = max(ar[i][1] + d[j], d[j + ar[i][0]]);
		}
	}
	cout << d[k];

	return 0;
}

 

다 풀고 풀이를 확인하던 중에 어떤 분이 1차원 dp로 푸는 걸 보고 따라해봤다.

		for (int j = k - ar[i][0]; j >= 0; j--) {
			d[j + ar[i][0]] = max(ar[i][1] + d[j], d[j + ar[i][0]]);
		}

 

전체 k에서 가방의 무게를 빼주고 뒤에서부터 인덱스를 채우는 식이다.

i가 끝날때마다 가방 하나씩 체크하고 다시 갱신하는 식이라 시간복잡도가 훨씬 줄어듦을 예상할수 있다.

참신한 방법이라 생각했다.

 

냅색 문제는 dp의 대표적인 유형이라는데 비슷한 유형의 문제가 나오면 잘 풀 수 있도록 노력해봐야겠다.