BOJ 12865: 평범한 배낭(0-1 Knapsack Problem)

✔ 문제 링크

BOJ 12865: 평범한 배낭

---

✔ 문제해결전략

• 0-1 Knapsack Algorithm
• Dynamic Programming

---

✔ 해결과정

가방에 담을 수 있는 물건의 무게에 제한이 있을 때, 가방에 담긴 물건들의 가치 합의 최댓값을 구해야 한다.

가장 먼저 생각해 볼 수 있는 방법은 각 물건을 넣는 경우, 넣지 않는 경우를 모두 탐색해 보는 것이다. 그런데 1 <= N <= 100이므로 완전 탐색을 하면 worse case에 O(2^n)이므로 바로 time out이다. 물건들의 무게가 배수 관계인 경우 greedy로 탐색 범위를 줄여볼 수 있겠으나 이 문제는 0-1 knapsack problem이므로 그럴 수도 없다. 그러면 DP로 메모리와 시간 복잡도를 교환해 봐야겠다는 생각을 해볼 수 있다. 근데 점화식 잡기가 무지 어렵다.

우선 가방의 여유 무게와 가치 두 가지 모두 고려해야 하므로 변수가 2개 필요하다는 생각을 해볼 수 있다. 그러면 아래와 같이 점화식을 세워보자.

• D(i, k) : i 번째 물건까지 사용하였고 가방의 무게가 k일 때 가방에 담긴 물건들의 가치의 최댓값

  Input으로 주어진 n개의 물건에 대해 1번부터 n번까지 순차적으로 탐색해나가며 위 점화식의 테이블을 채워볼 것이다. 탐색 과정에서 아래 2가지 경우를 고려해야 한다.

1. 현재 탐색하고 있는 물건을 가방에 담을 수 있는지

• 현재 물건을 가방에 넣어도 최대 무게를 초과하지 않으면 가방에 넣을 수 있다. 하지만 현재 물건을 가방에 넣었을 때 가방의 최대 무게를 초과한다면 이 물건을 가방에 넣을 수 없다.

2. 물건을 가방에 담을 수 있을 때, 담는 경우와 담지 않는 경우 중 어느 경우에 가치가 최대가 되는지

• 물건을 가방에 담을 수 있다고 해서 무조건 담아야 하는 것은 아니다. 이 물건 대신 다른 물건을 넣었을 때 가치가 더 높을 수 있기 때문이다.

위 2가지 사항을 고려하여 테이블을 채워나갈 건데 1번을 확인하기 위해서는 기존에 가방에 담긴 물건들의 무게 합 을 알고 있어야 한다. 그래서 가방에 넣을 수 있는 무게가 1인 경우부터 최대 무게인 경우까지 모두 탐색을 하였다.

for(int i=1;i<=n;i++) {
	for(int j=1;j<=k;j++) {
		if(bag[i].first<=j) {
			d[i][j] = max(d[i-1][j-bag[i].first] + bag[i].second, d[i-1][j]);
		}
		else {
			d[i][j] = d[i-1][j];
		}
	}
}

바깥 for문은 1번 ~ n번 물건을 탐색하기 위한, 안 for문은 가방에 넣을 수 있는 무게가 1인 경우부터 최대 무게인 경우까지를 탐색하기 위한 반복문이다. 넣을 수 있는지 여부를 판단하고, 넣을 수 있다면 넣지 않고 가방을 채운 경우와 넣는 경우 중 최적값을 선택한다.

---

✔ 정답 Code

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

pair<int,int> bag[101]; // weight, value
int d[101][100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	for(int i=1;i<=n;i++) {
	    // weight, value
		cin >> bag[i].first >> bag[i].second;
	}
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=k;j++) {
			if(bag[i].first<=j) {
				d[i][j] = max(d[i-1][j-bag[i].first] + bag[i].second, d[i-1][j]);
			}
			else {
				d[i][j] = d[i-1][j];
			}
		}
	}
	cout << d[n][k];
}
	

---

✔ Comment

준서가 아니라 21.03의 백윤재인데,,

---

✔ 참고자료

https://yabmoons.tistory.com/571