🎒 배낭 문제 (Knapsack Problem)

무게 제한이 있는 배낭에 물건들을 최대한 효율적으로 넣는 방법을 찾는 알고리즘

이전에 배낭 문제를 몇 번이나 이해하려 노력했지만 포기했고, 드디어 이해하여 포스팅을 적는다.

아래 문제를 참고하여 코드를 작성하였다.

🔗 백준 12865번 - 평범한 배낭

📌 배낭 문제 조건

각 물건은 무게와 가치를 가진다.
배낭에는 최대 무게 제한이 있다.
물건을 선택하여 가치의 합이 최대가 되도록 해야 한다.

대표적인 동적 계획법(DP) 문제로, 알고리즘 문제풀이에서 자주 등장하는 개념이다.

🛠 문제 접근 방식

✔️ DP 테이블 구성

dp[i][j]

→ i번 물건까지 고려했을 때, 무게 j를 채웠을 때의 최대 가치

i (물건) \ w (무게)	0	1	2	3
0 (물건 없음)
1 (물건1까지 고려)
2 (물건2까지 고려)

DP 테이블은 위와 같이 생성되며,

세로는 몇 번 인덱스 물건까지 고려하여 선택할 것인지, 가로는 가방에 담을 수 있는 수용 무게를 몇으로 설정할 것인지를 의미한다.

🧐 문제의 목표는 제한된 무게에서 최대 가치를 구하는 것인데, 왜 수용 무게를 0부터 고려하며 테이블을 구성할까?

간단하게 예시를 들어보겠다.

가방에 넣을 수 있는 총 무게: 10kg
내가 시도해 볼 물건의 무게: 4kg

위와 같은 조건에서 내가 시도해 볼 물건(4kg)을 가방에 넣었을 때, 가방은 6kg의 무게를 더 수용할 수 있다.

이때, DP 테이블에서 만든 “수용 무게가 6kg일 때의 최대 물건의 가치”를 사용할 수 있는 것이다.

아직은 잘 와닿지 않지만, 아래 예시 문제를 보면 자연스럽게 이해할 수 있다.

✔️ 상태 정의

i: 현재 고려 중인 물건 인덱스
j: 현재 고려 중인 배낭의 최대 무게

✔️ 점화식

if (weight[i] <= j) {
    dp[i][j] = Math.max(dp[i-1][j], value[i] + dp[i-1][j - weight[i]]);
} else {
    dp[i][j] = dp[i-1][j];
}

weight[i] <= j

→ 현재 물건을 넣을 수 있을 때,

👉 넣지 않는 경우 vs 넣는 경우 중 더 큰 가치 선택
weight[i] > j

→ 현재 물건을 넣을 수 없을 때,

👉 그냥 이전까지의 최선값을 유지

✅ 예시 문제

가방 최대 무게: 5kg
물건 3개:

번호	무게	가치
1번	2kg	3
2번	3kg	4
3번	4kg	5

1. DP 테이블 생성

i (물건의 개수) \ w (무게)	0	1	2	3	4	5
0 (물건 0개)
1 (물건 1개)
2 (물건 2개)
3 (물건 3개)

DP 테이블의 크기는 물건의 개수와 최대 무게보다 1 높은 크기로 설정된다.

0개의 물건을 고려하는 경우와 최대 가방 무게가 0인 경우를 고려하기 때문이다.

즉, 가방이 아예 비어있는 경우를 의미한다.

이전 인덱스를 참고하여 현재 인덱스를 갱신하는 DP 테이블 특성상 아무것도 넣지 못하는 경우가 필요하다.

2. DP 테이블 채우기

인덱스를 증가시켜가며 i번 물건까지 고려하여 w무게까지 수용할 수 있을 때의 최대 가치를 찾는다.

경우는 “현재 수용 가능 무게에서 새로운 물건을 담을 수 있는지, 없는지”에 따라 2가지로 나눌 수 있다.

새로운 물건을 담을 수 없다면, dp[i-1][w] 값을 그대로 가져온다.
새로운 물건을 담을 수 있다면, 넣는 경우와 안 넣는 경우 중 더 큰 가치를 선택한다.

i\w	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3

먼저 i == 0인 행에서는 아무 물건도 넣을 수 없는 상태이므로 0이 할당된다.

또한 w == 0인 열에서도 가방 무게가 0이기 때문에 아무 물건도 넣을 수 없다.

[1,2]에서 처음으로 값이 들어간다.

1번 물건은 2kg이기 때문에, w 인덱스가 2일 때(수용 가능 무게가 2kg)부터 가방에 넣을 수 있는 경우가 생긴다.

“새로운 i번 물건을 담을 수 있는 경우”

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3

[2,3]에서는 2번 물건을 고려할 수 있고, 무게 3kg이기 때문에 w=3부터 넣을 수 있다.

2번 물건을 넣지 않는 경우: dp[1][3] → 3
2번 물건을 넣는 경우: value[2] → 4

👉 2번 물건을 넣는 것이 더 가치가 크기 때문에 넣는다.

남은 공간을 고려하는 경우

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4

dp[2][5]를 채워야 하는 상황.

2번 물건(3kg, 가치 4)을 넣고 남은 무게는 2kg.

이때 남은 2kg 공간에 대해 dp[1][2] 값을 참고해야 한다. (i-1까지 고려)

2번 물건을 넣지 않는 경우: dp[1][5] → 3
2번 물건을 넣는 경우: value[2] + dp[1][2] → 4 + 3 = 7

👉 7이 더 크기 때문에 넣는다.

최종 테이블은 다음과 같다:

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	3	4	5	7

🖥️ 풀이 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int input = Integer.parseInt(st.nextToken());  // 물건 개수
        int limit = Integer.parseInt(st.nextToken());  // 배낭 최대 무게

        int[] weight = new int[input + 1];  // 물건 무게
        int[] value = new int[input + 1];   // 물건 가치

        for(int i = 1; i <= input; i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st2.nextToken());
            value[i] = Integer.parseInt(st2.nextToken());
        }

        int[][] dp = new int[input + 1][limit + 1];
        // dp[i][j] = i번째 물건까지 고려했을 때, 무게 j를 채웠을 때의 최대 가치

        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                if(i == 0 || j == 0) continue;

                if(weight[i] <= j){
                    dp[i][j] = Math.max(
                        dp[i-1][j],
                        value[i] + dp[i-1][j - weight[i]]
                    );
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[input][limit]);
    }
}

⏰ 시간복잡도

이중 for문 → O(N * K)

(N: 물건 수, K: 최대 무게 제한)
메모리 사용도 dp[N+1][K+1] 만큼 필요

⚠️ N, K가 커지면 메모리 초과 주의!