[백준] #12865 평범한 배낭(Python/Java)

중요하거나 어려웠던 문제에 대해 작성합니다.

• 2차원 DP
• Knapsack 문제

문제 📝

가장 기본적인 배낭 문제(Knapsack) 이여서 선정하였다. 문제의 경우 다음 링크를 클릭하면 된다.

해결 💡

Knapsack problem

나무위키 참고

배낭 문제는 크게 물건을 잘라서 넣을 수 있는 분할이 가능한 배낭 문제와 불가능한 문제(0-1 배낭 문제) 로 구분됩니다. 전자는 그리디 알고리즘으로 해결하고, 후자는 DP(Dynamic Programing) 이나 백트레킹으로 해결합니다.

해당하는 백준 문제 #12865는 물건들을 잘라서 넣을 수가 없습니다. 그래서 넣거나 안넣거나 둘만 가능하기에 0-1 배낭 문제에 속합니다.

0-1 Knapsack problem

위키피디아에 따라, 해당 문제의 pseudocode는 아래와 같습니다.

// 입력:
// 가치 (배열 v)
// 무게 (배열 w)
// 물건 수 (n)
// 최대 무게 (W)

array dp[0..n, 0..W];

for j from 0 to W do:
    dp[0, j] := 0
for i from 1 to n do:
    dp[i, 0] := 0

for i from 1 to n do:
    for j from 1 to W do:
        if w[i] > j then:
            dp[i, j] := dp[i-1, j]
        else:
            dp[i, j] := max(dp[i-1, j], dp[i-1, j-w[i]] + v[i])

과정에 따라

• 우선, dp를 실행할 2차원 배열을 만듭니다. 이 때 행 인덱스는 0 에서 n 까지의 범위를 갖고, 열 인덱스는 0 에서 W 까지의 범위를 갖습니다.

• 모든 배열의 값을 0으로 초기화 합니다.

• 행 인덱스 i 의 역할은 담는 물건의 인덱스, 열 인덱스 j 의 역할은 담는 무게를 의미합니다. 그리고 dp[i, j] 는 가치가 들어갑니다.

• dp 에서 현재 물건 인덱스 i 와 무게 j 에서 최대 가치를 구하는 상황을 생각해보면 두가지 과정을 생각할 수 있습니다.

  1. i 번째 물건 그냥 넘기기
  2. i 번째 물건 추가하기

• 너무 당연한 소리죠? 그럼 각각은 코드로 어떻게 구현하는지 보겠습니다.
  그리고 둘 중에 더 큰 것을 택하면 됩니다.

  1. 물건을 그냥 넘기므로 무게가 변하지 않습니다. 무게는 현재 무게와 같은 값을 가져옵니다. 즉, dp[i-1, j] 입니다.
  2. 이번에는 사용합니다. 물건을 추가했을 때 물건을 포함한 무게인 j 가 목표이므로 가져올 값은 i 번째 물건의 무게 w[i] 를 뺀 것에서 가져와야 구할 수가 있습니다. 다만, 물건을 추가하기에 값에는 추가한 물건의 가치 v[i] 를 더해야 됩니다. 즉, dp[i-1, j-w[i]] + v[i] 입니다.

• 근데... 정말 극단적으로 생각해서 j 는 1인데, w[i] 가 1억이라면..? 기준보다 무거운 물건에 대해서는 패스하도록 합니다. 즉, dp[i-1, j] 입니다.

위와 같은 과정을 활용하여 문제를 해결하면 아래와 같습니다.

Python 🐍

import sys

N, K = map(int,sys.stdin.readline().rstrip().split())
DP = [[0 for j in range(K + 1)] for i in range(N + 1)]
bag = [(0, 0)]

for _ in range(N):
	W, V = map(int,sys.stdin.readline().rstrip().split())
	bag.append((W, V))

for i in range(1, N+1):
	w, v = bag[i]
	for j in range(1, K+1):
		if w > j:
			DP[i][j] = DP[i-1][j]
		else:
			DP[i][j] = max(DP[i-1][j], DP[i-1][j-w]+v)

print(DP[N][K])

Java ☕️

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] dp = new int[N + 1][K + 1];
        int[][] bag = new int[N + 1][2];

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            bag[i][0] = Integer.parseInt(st.nextToken());
            bag[i][1] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 1; i <= N; i++) {
            int w = bag[i][0];
            int v = bag[i][1];

            for(int j = 1; j <= K; j++) {
                if(w > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
                }
            }
        }

        System.out.println(dp[N][K]);
        br.close();
    }
}