[백준] 12865 평범한 배낭 (복습 + DP 개선)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

DP 냅색 문제입니다.

i번째 보석까지 가방에 넣을 수 있을때,  무게 k 가방에 넣을 수 있는 최대 무게를 저장합니다.

#include <iostream>
#include <vector>
using namespace std;

int weight[101];
int value[101];
int dp[101][100001];

int main() {
	int n, k, w, v;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> w >> v;
		weight[i] = w;
		value[i] = v;
	}
	for (int i = 1; i <= n; i++) { //보석 i번째까지 사용가능
		for (int j = 1; j <= k; j++) { //가방무게가 j일때
			if (j >= weight[i]) {  //만약 i번째 보석을 가방에 넣을 수 있으면
            	//i번째보석의 가치 + 남아있는 용량으로 넣을 수 있는 보석의 가치
                //i번째 보석을 안넣었을때의 보석의 가치 
                //중 큰 값을 저장합니다.
				dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j]);
			}
			else {
            	//만약 i번째 보석을 가방에 넣을 수 없으면
                //보석을 넣지 않았을때 가치를 저장합니다.
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[n][k];
}

============================================================================================

위의 방법으로는 2차원 배열로 DP를 사용했습니다.

i번째 보석을 넣을 수 있으면 넣을지 말지를 비교해 업데이트 합니다.

 

2차원 배열이 아니라 1차원 배열로도 DP를 사용할 수 있습니다.

#include<iostream>
using namespace std;


int n, k, w, v, dp[100001], i;
int main() {
	cin >> n >> k;
	for (i = 1; i <= n; i++) { //보석의 횟수만큼 반복 i번째 보석까지 넣을 수 있을때,
		cin >> w, cin >> v; //i번째 보석의 무게와 가치
		for (int j = k; j >= w; j--) { //업데이트의 후보는 i번째 보석의 무게부터, 총 가방의 무게까지
			dp[j] = max(dp[j], v + dp[j - w]);//i번째 보석을 넣을때와 안넣을때를 비교, 업데이트
		}
	}
	cout << dp[k];
}

i번째 보석을 넣을때 업데이트 후보는 정해져 있으므로,

1부터 k까지 확인을 할 필요가 없습니다.