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

1. 문제 링크

12865번: 평범한 배낭

2. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX_N 105
#define MAX_W 100005
using namespace std;
int dp[MAX_N][MAX_W];
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,k;
	cin >> n>>k;
	vector<int> weight(n+1);
	vector<int> value(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> weight[i] >> value[i];
	}
	for (int i = 0; i <= n; i++) {
		for (int w = 0; w <= k; w++) {
			if (i == 0)dp[i][w] = 0;
			else if (w == 0)dp[i][w] = 0;
			else if (weight[i] > w) {
				dp[i][w] = dp[i - 1][w];
			}
			else{
				dp[i][w] = max(dp[i - 1][w - weight[i]] + value[i], dp[i - 1][w]);
			}
		}
	}
	cout << dp[n][k];

}
//현재 보석의 무게가 배낭 한도보다 무거울 경우>> 바로 위 칸 가져옴
//지금까지 있었던 거 빼고 넣을 수 있잖아?아니 비워도 못 넣을 때
//
//아닐 경우>>넣는게 이득인지 안 넣는게 이득인지 계산
//마지막 칸의 값이 최종적인 답

3. 노트

3-1.Dynamic programming을 이용한 knapsack 문제의 해결

가방 채우기 문제(Knapsack problem)는 Brute force, greedy 등 여러가지 방법으로 풀 수 있지만, 기본적으로 DP를 쓰는 경우가 많다고 한다. 이 문제를 DP를 써서 표를 이용하여 풀려고 할 때, 표의 행은 물건 배열의 인덱스(r번째 물건), 표의 열은 가방의 무게 한도로 설정하여야 한다.

dp[i][w]: 가방에 넣을 수 있는 최대 무게가 w라고 할 때, 0~i번째 아이템 중 골라담기하여 얻을 수 있는 최대 이익

dp[i][w]를 설정할 때, 만약 i번째 아이템이 가방의 무게 한도보다 무겁다면 지금까지 가방에 넣은 아이템들을 다 비우고 지지고볶고 한다 해도 못 넣겠지? 어차피 i번째 아이템은 못 넣으니 dp[i][w]=dp[i-1][w]이다.

만약 i번째 아이템을 가방에 넣을 수 있다면? i번째 아이템을 가방에 넣는 경우와 넣지 않는 경우로 나눠 생각한다. i번째 아이템을 담을 경우 가방에서 빼야 할 아이템이 생길 수도 있기 때문이다.
따라서 이 때의 dp[i][w]=max(i번째 아이템을 넣었을 때의 이익+dp[i-1][w-(i번째 아이템의 무게)],dp[i-1][w]이다.

cf)점화식