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

유형	난이도	완료일	링크	특이사항
DP/냅색	G5	23/03/11	https://www.acmicpc.net/problem/12865	오래 걸림, 냅색 알고리즘 참조

 

 

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

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

int main(void)
{
	int n, k;
	cin >> n >> k;
	
	for(int i =1; i<=n; i++)
		cin >> weight[i] >> value[i];
		
	for(int i=1; i<=n; i++)
	{
		for(int j = 1; j<=k; j++)
		{			
			if(weight[i] > j)
				bestValue[i][j] = bestValue[i-1][j];
			else 
				bestValue[i][j] = max( bestValue[i-1][j], bestValue[i-1][j-weight[i]] + value[i] );
		}
	}

	cout << bestValue[n][k];
}

 냅색 알고리즘을 찾아보지 않았으면 이렇게 풀기 쉽지 않았을 것 같다.

[물건 idx] X [무게(0~K)] 로 이루어진 배열을 만들고 무게 0부터 K까지 증가시켜가며 구한다는 생각을 아예 못했다. n-1로 n을 구하는 방법이 무엇일지 고민했지만 계속 물건이 1개일 때, 2개일 때… 와 같은 식으로 생각하고 2차원 배열을 사용하더라도 [무게] X [가치]를 나타내는 배열밖에 생각하지 못했다.

 점화식은 물건 배열을 순회하며, 하나의 물건당 무게가 0~k일때까지 해당 물건을 포함할 수 있을 때의 최대 value를 찾는 식으로 구성된다. 특정 물건이, 특정 무게 제한일 때 추가될 수 있다면 추가하지 않고 이전 물건을 포함할 수 있는 경우의 최댓값을 선택했을 때의 값, 이전 물건까지 포함할 수 있고 현재 물건의 무게만큼 현재 무게 제한을 감소시킨 경우의 최댓값에 현재 물건의 가치를 더한 값 중에서 더 큰 값을 저장한다. 특정 무게 제한일 때 추가될 수 없다면(특정 물건의 무게가 현재 무게 제한보다 크다면)현재 물건이 추가되기 전, 즉 이전 물건을 포함할 수 있는 경우(무게 제한은 똑같이 유지)의 최댓값을 저장한다. 이렇게 값을 저장해나가면 DP[n][k]에 가능한 최대 합이 저장된다.

 n-1으로 n을 구하는 DP의 특성이 냅색 알고리즘에선 무게를 핵심으로 하여 드러나는 것 같다. 나는 계속 무게를 하나의 장애물처럼 생각했다. DFS문제처럼 해결하면서 어떻게 무게 제한이라는 요소를 반영할지 많이 고민했다. 무게 제한이라는 특정 조건을 장애물로만 생각하는게 아니라 유연하게 그것을 문제 해결의 방식 중 하나로 녹였어야 했다. DP[i][j] 가 DP[i-1][j-weight[i]] + value[i] 로 표현되는 점화식은 정말 생각을 못했다. 특정 물건을 추가하기 위해서 어떻게 최적의 물건을 골라 제외할 것인가를 많이 고민했는데 DP에서 막힐때면 항상 가장 많이 고민한 부분이 DP자체의 특성으로, 하나의 점화식으로 해결되는 것 같다.

 

 

더 최적화 된 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int w[101]; // 무게
int v[101]; // 가치
int dp[101];

int N, K; // 물품의 수 N, 준서가 버틸 수 있는 무게 K

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	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 = K; j >= 1; j--) {
			if (w[i] <= j) { // 넣을 수 있다면?
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
                // 그 물건을 넣었을 때와 넣지 않았을 때 중 더 큰 값으로 초기화
			}
		}
	}

	cout << dp[K];

	return 0;
}

//https://chanhuiseok.github.io/posts/improve-6/

 dp 배열을 2차원으로 만들 필요 없이 1차원 배열로 해결도 가능하다. 이 방법이 메모리도 훨씬 적게 쓰고 빠르다.

핵심은 DP[물건 idx][무게 제한] 에서, ‘물건 idx’부분이 결국 -1 한 지점까지만 참조한다는 점을 이용하는 것이다.

즉 2차원 행렬이지만 n번째 행을 만들 때 최대 n-1행 까지만 참조하기 때문에 결국 1차원 배열로 만들고 해당 배열의 값을 갱신하기 위해 현재 배열 값을 참조하여 새로운 배열 값을 구하면 똑같은 효과를 얻을 수 있다.