[C++] BOJ(백준) 12865 평범한 배낭

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

12865번: 평범한 배낭

 

dp 문제 유형 중 하나인 배낭 문제다.

배낭 문제는 물건의 무게와 가치가 주어지고 가방의 무게가 주어졌을 때,

가방에 담은 물건들의 가치가 최대가 되도록 하는 것이다.

 

dp 배열을 가방에 담은 물건의 개수, 가방의 무게 제한에 대한 2차원 배열로 만든다.

n개의 물건을 담을 수 있을 때, n번 쨰 물건을 담는다고 생각하자.

n번 물건의 무게보다 가방의 무게 제한이 작다면, 해당 무게 제한에서 n - 1개의 물건을 담을 수 있는 가치를 저장한다.

크거나 같다면  (해당 무게 제한에서 n - 1개의 물건을 담을 수 있는 가치)와

(n번 물건의 무게를 뺀 상태의 n - 1개의 물건을 담을 수 있는 가치 + n번 물건의 가치) 를 비교한다.

 

점화식을 세우면 아래와 같다.

#include <iostream>
using namespace std;

int n, m;
int dp[101][100001];
pair<int, int> thing[101];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int a, b;	cin >> a >> b;
		thing[i] = { a, b };
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (thing[i].first > j) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - thing[i].first] + thing[i].second);
		}
	}

	cout << dp[n][m];
}

(✿◡‿◡)