Computer Science & Engineering

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

문제

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

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

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

풀이

문제 설명에 나와 있듯이 유명한 냅색 문제이다. 무게가 정해져 있을 때 가치를 최대로 배낭을 채우는 문제이다. DP문제로 유명한 이 문제는 다음 점화식으로 풀 수 있다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + cost[i]);

이 점화식에서 i는 i번째 물건을 뜻한다. j는 무게이다. 즉 dp[i][j]가 뜻하는 것은 i번째 물건을 무게가 j이하로 채울 때 최대 가치의 합을 나타낸다. 따라서 dp[i-1][j]은 i번째 물건을 넣지 않는다는 뜻이고 dp[i-1][j-weight[i]] + cost[i]는 i번째 물건을 넣는다는 것이다. 따라서 i번째 물건의 무게(weight[i])를 j에서 뺀 값에 i번째 물건의 가치(cost[i])를 더한 값을 뜻한다. 즉 위의 점화식이 나타내는 것은 i번째 물건을 넣었을 때와 넣지 않았을 때의 값중 더 큰 값을 저장한다는 것이다. 이 점화식을 이용하여 작성한 코드는 다음과 같다.

소스 코드

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int,int>> arr;
int dp[101][100001]; //101은 물건의 개수, 100001은 무게의 최대값
int w[101]; //i번째 물건의 무게
int value[101]; //i번째 물건의 가치

int main() {
	int N, K; cin >> N >> K;
	for(int i = 1; i <= N; i++) {
		cin >>  w[i] >> value[i];
	}

	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= K; j++) {
			if(j < w[i]) //j값보다 i번째 물건의 무게가 더 큰 경우 배낭에 넣을 수 없다.
				dp[i][j] = dp[i-1][j]; //따라서 물건을 넣지 않는다.
			else { //물건이 들어갈 경우
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + value[i]);
				//물건을 넣는 경우와 넣지 않은 경우 중 더 큰 가치 선택
			}
		}
	}
	cout << dp[N][K];
}

이렇게 문제를 풀 경우 상당한 메모리가 소모도니다. 이 코드를 보면 i번째 dp배열은 i-1번째 dp배열로부터 계산되는 것을 알 수 있다. i값은 2가지만 사용한다. 또 j번 인덱스만 봤을 때 더 큰 값이거나 같은 값으로 유지된다. 그림으로 나타내면 다음과 같다.

그렇다면 1개의 배열로 사용할 수 있지 않을까? 만약 j를 큰 값부터 줄여간다면 작은 값들에 영향을 주지 않고 갱신할 수 있을 것이다 (큰 값부터 한다는 것은 만약 작은 값에서 j-w[i]와 같이 큰 값으로 갱신 된다면 이후에 큰 값을 갱신할 때 이미 영향을 받은 값을 다시 갱신할 수 있기 때문이다). 코드로 나타내면 다음과 같다.

소스 코드

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

using namespace std;

const int MN = 101;
const int MK = 100101;

int w[MN], cost[MN];
int dp[MK]; //1차원 배열

int main() {
    int N, K;   cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        cin >> w[i] >> cost[i];
    }
    
    for(int i = 1; i <= N; i++) {
        for(int j = K; j >= 0; j--) { //큰 값부터 작은 값으로 
            if(j >= w[i]) //배낭에 넣을 수 있을 때만
                dp[j] = max(dp[j], dp[j-w[i]] + cost[i]); //더 큰 값으로 갱신
        }
    }

    cout << dp[K];
}

채점 결과

위의 결과가 1차원 배열을 사용한 경우가 아래 결과가 2차원 배열을 사용한 경우이다. 메모리가 거의 20배 차이 나는 것을 알 수 있다.