[백준] 알고리즘 12865번 - 평범한 배낭 문제

문제

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[101][100001];
int arr[101][2];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> arr[i][0] >> arr[i][1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (arr[i][0] <= j) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i][0]] + arr[i][1]);
			}
			else dp[i][j] = dp[i-1][j];
		}
	}
	cout << dp[n][k];

}

풀이

동전1과 비슷한 유형의 문제입니다.

다만 다른점은 동전에서는 dp n의 개수들을 합쳐서 저장하였다면, 현재 이문제는 물건을 하나만 사용하여 가중치들의 최대값을 비교하여 저장해줘야 하는 다른점이 있다.

 

1. k까지 동전처럼 만들 수 있는 경우의 수를 각각 저장해준다 생각해봅시다. 예시에는 k=7이닌간

	0	1	2	3	4	5	6	7
6BAG	0	0	0	0	0	0	가중치13	13
4BAG	0	0	0	0	8	8

당연히 6의 무게의 가방은 0~5까진 6을 이용해서 만들 수 없으니 0이다. 이후 6이후부터는 만들기 가능하닌깐 그에 따른 가중치를 저장해준다.

 

2. 가중치가 최대인값을 저장하여줘야하기 때문에

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i][0]] + arr[i][1]);

점화식을 작성하면 이렇게 작성할 수 있습니다.

그 이전의 가방을 그대로 사용할 것인가? 아니면 가방을 추가할 것인가 그것을 고민하여 저장합니다.

dp[i][j]에 dp[i-1][j] 값을 비교하는 이유는 사용할 물건을 중복해서 사용할 수 있는 점이 있으므로, 이전의 값을 그대로 사용하면서 비교합니다.