[백준/C++] 12865번: 평범한 배낭

문제

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

12865번: 평범한 배낭

---

문제 요약

무게 W와 가치 V를 갖는 물건 N개가 있을 때, 해당 물건을 배낭에 넣어 V만큼 즐길 수 있다.

 

최대 K만큼의 무게만을 넣을 수 있는 배낭을 들고 여행을 할 때, 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 출력한다.

---

코드

#include<iostream>

#define MAX_N 100
#define MAX_K 100000

using namespace std;

int n, k;

int dp[MAX_N + 1][MAX_K + 1]; 
// dp[i][j] : 배낭에 i번 물건까지 넣을 수 있을 때, 배낭에 담을 수 있는 무게가 j인 경우 가치의 최대 값

int w[MAX_N + 1]; // w[i]: i번 물건의 무게
int v[MAX_N + 1]; // v[i]: i번 물건의 가치

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

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			// i번 물건을 가방에 넣을 수 있다면
			if (j >= w[i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
				// i-1번 물건까지 넣을 수 있을 때와 i번 물건을 가방에 넣었을 때의 가치를 비교 
				// dp[i - 1][j - w[i]]: i번을 넣을 수 있을 때의 가치의 최대 값 (이 상황에서 i번 물건을 넣어야함)
			}
			// i번 물건을 가방에 넣을 수 없다면
			else {
				dp[i][j] = dp[i - 1][j];
				// i-1번 물건까지 넣을 수 있는 경우의 최대값과 변함 x
			}
		}
	}

	cout << dp[n][k];


	return 0;
}

---

코드 설명

2차원 dp를 이용해 문제를 해결한다.

 

입력을 받은 순서대로 물건에 번호를 붙이고, w[i]에 i번 물건의 무게, v[i]에 i번 물건의 가치를 저장한다.

 

dp[i][j]를 "배낭에 i번 물건까지 넣을 수 있고, 담을 수 있는 무게가 최대 j일 때, 가치의 최대 값"으로 설정한다.

 

for문 2번을 이용하여, dp테이블을 차례대로 채운다.

 

< dp[i][j]를 채우는 과정 >

1. i번 물건의 무게가 무거워 배낭에 담을 수 없는 경우

=> i-1번 물건까지 배낭에 넣을 수 있고,  담을 수 있는 무게가 최대 j일 경우와 같다. (변함이 없다.)

 

2. i번 물건의 무게가 가벼워 배낭에 담을 수 있는 경우

=> i-1번 물건까지 배낭에 넣을 수 있고, 담을 수 있는 무게가 최대 j일 경우와, i번 물건을 넣을 수 있을 때의 가치의 최대 값에 i번 물건을 넣었을 때의 가치를 비교하여 큰 값을 저장한다.

+ i번 물건을 넣을 수 있을 때의 가치의 최대 값: dp[i - 1][j - w[i]]

 

dp[n][k]를 출력한다.