배낭 문제 (Knapsack Problem)

Knapsack Problem

1. 배낭에 담을 수 있는 최대 무게가 정해져 있고,
2. 일정 가치와 무게가 정해져 있는 짐들을 배낭에 담을 때
3. 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제

종류

1. 물건을 쪼갤 수 있는 배낭 문제 (Fraction Knapsack Problem)
2. 물건을( 쪼갤 수 없는 배낭 문제 (0/1 Knapsack Problem)

Fraction Knapsack Problem

물건을 쪼갤 수 있기 때문에, 가치가 큰 물건부터 담고, 나머지 공간은 그 다음 가치의 물건을 쪼개서 담는 그리디 알고리즘 으로 처리할 수 있다.

0/1 Knapsack Problem

물건이 쪼개지지 않기 때문에, 동적 계획법 을 이용한다.

물건의 무게와 가치가 아래의 표와 같을 때

물건	1	2	3	4
무게	6	4	3	5
가치	13	8	6	12

0 ~ 물건의 갯수까지인 N + 1개와 0~최대 무게까지인 K + 1개의 2차원 배열을 만들고

	0	1	2	3	4	5	6	7
0
1
2
3
4

첫 번째 물건만 넣을 수 있을 때, 가방의 최대무게에 따른 이윤이다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2
3
4

두 번째 물건까지 넣을 수 있을 때, 가방의 최대무게에 따른 이윤이다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3
4

세 번째 물건까지 넣을 수 있을 때, 가방의 최대무게에 따른 이윤이다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4

3행 7열이 이 알고리즘의 핵심이다. 가방의 최대 무게가 7 일 때, 세 번째 물건을 넣고 나서도 가방의 무게가 4가 남는다. 이 때 이전 행에서 최대 무게가 4일때의 이윤을 더해주면 물건 3개를 무게 7까지 담았을 때의 최대 이윤을 알 수 있다.

네 번째 물건까지 넣을 수 있을 때, 가방의 최대무게에 따른 이윤이다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

마지막 물건까지 다 담았을 때, 배열의 마지막 행, 마지막 열이 최대 이윤을 나타낸다.

위의 과정을 점화식으로 나타내면 아래와 같다.

각 물건의 가치 : V[i]
각 물건의 무게 : W[i]
해당 물건까지 고려했을 때의 최대 이윤 : dp[N][K] 일 때

// 현재 물건의 무게보다 현재 가방의 무게가 작으면 (담을 수 없으면)
if (w[i] > j)   dp[i][j] = dp[i-1][j];          // 이전 물건까지의 가치 중 현재 무게에 대한 가치 값
// 현재 물건의 무게보다 현재 가방의 무게가 크면 (담을 수 있으면)
else            dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j - w[i]]); // (현재 물건의 가치 + 이전 물건까지의 가치 중 현재 가방의 무게 - 현재 물건의 무게)와 이전 물건까지의 가치 중 현재 무게에 대한 가치, 둘 중 큰 값

구현

아래의 코드는 위의 점화식을 최적화 한것으로, 연산 시간과 메모리 관리 둘 다 이득이다.

#include <cstdio>
using namespace std;
int main()
{
    // 물건 갯수
    int N;
    // 최대 무게
    int K;
    // 현재 물건의 무게
    int w;
    // 현재 물건의 가치
    int v;
    scanf("%d %d", &N, &K);
    // 0 ~ 최대 무게까지의 최대 이윤
    int dp[K + 1] = {};
    for (int i = 1; i <= N; ++i)
    {
        // 1 ~ N (물건의 갯수)만큼  물건의 무게와 가치를 입력 받는다.
        scanf("%d %d", &w, &v);
        // 최대 무게 ~ 현재 물건의 무게까지 반복
        // (이 때 현재 물건의 무게가 최대 무게보다 크면 자동으로 스킵)
        // (또한 내림차순으로 현재 물건의 무게까지만 반복하기때문에 현재 물건의 무게보다 작은 무게는 알아서 이전값으로 유지됨)
        for (int j = K; j >= w; --j)
        {
            // 만약 현재 물건의 가치 + (현재 무게 - 현재 물건의 무게)만큼의 이전 물건까지의 가치가 
            // 이전 물건까지의 현재 무게만큼의 가치 보다 크면 최신화
            if (v + dp[j - w] > dp[j]) dp[j] = v + dp[j - w];
        }
    }
    // 최대 무게일 때의 최대 이윤 출력
    printf("%d\n", dp[K]);
}

참조

알고리즘 이론 : 테리의 일상
알고리즘 코드 : pentagon03 님의 BOJ-12865 풀이