[알고리즘 / 백준] 12865 - 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

문제는 위와 같으며 이 문제는 배낭의 무게가 0 ~ K 인 경우를 모두 확인하는 방식으로 문제를 풀 수 있습니다.

 

예제를 바탕으로 살펴보면 처음에는 0부터 7까지 모두 가치가 0인 배열로 초기화를 하고 이후 무게(w)와 가치(v)가 주어지면 w 보다 작은 무게의 경우는 기존 가치를 그대로 가져가고 w 보다 크거나 같을 때는 w 를 뺀 무게의 가치와 주어진 가치(v)를 더해 이전 가치와 비교해 더 큰 값으로 가치를 정합니다. 

 

그림으로 보면 다음과 같습니다.

1. w = 6, v = 13 인 경우

    - 0 ~ 5 까지는 기존 가치 그대로 추가

    - 6 인 경우 기존 무게 6의 가치(0) 와 무게 0의 가치(0) + 주어진 가치(13) 중 더 큰 가치로 지정 => 13

    - 7 인 경우도 기존 무게 7의 가치(0) 와 무게 1의 가치(0) + 주어진 가치(13) 중 더 큰 가치로 지정 => 13

 

2. w = 4, v = 8 인 경우

    - 0 ~ 3 까지는 기존 가치 그대로 추가

    - 4 인 경우 기존 무게 4의 가치(0) 와 무게 0의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 8

    - 5 인 경우 기존 무게 5의 가치(0) 와 무게 1의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 8

    - 6 인 경우 기존 무게 6의 가치(13) 와 무게 2의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 13

    - 7 인 경우 기존 무게 7의 가치(13) 와 무게 3의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 13

 

3. w = 3, v = 6 인 경우

    - 0 ~ 2 까지는 기존 가치 그대로 추가

    - 3 인 경우 기존 무게 3의 가치(0) 와 무게 0의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 6

    - 4 인 경우 기존 무게 4의 가치(8) 와 무게 1의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 8

    - 5 인 경우 기존 무게 5의 가치(8) 와 무게 2의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 8

    - 6 인 경우 기존 무게 6의 가치(13) 와 무게 3의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 13

    - 7 인 경우 기존 무게 7의 가치(13) 와 무게 4의 가치(8) + 주어진 가치(6) 중 더 큰 가치로 지정 => 14

 

4. w = 5, v = 12 인 경우

    - 0 ~ 4 까지는 기존 가치 그대로 추가

    - 5 인 경우 기존 무게 5의 가치(8) 와 무게 0의 가치(0) + 주어진 가치(12) 중 더 큰 가치로 지정 => 12

    - 6 인 경우 기존 무게 6의 가치(13) 와 무게 1의 가치(0) + 주어진 가치(12) 중 더 큰 가치로 지정 => 13

    - 7 인 경우 기존 무게 7의 가치(14) 와 무게 2의 가치(0) + 주어진 가치(12) 중 더 큰 가치로 지정 => 14

 

따라서 결과적으로 테이블의 가장 끝 무게의 가장 끝 가치가 정답이 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n, k = map(int, stdin.readline().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    w, v = map(int, stdin.readline().split())
    for j in range(1, k + 1):
        if j < w:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

print(dp[-1][-1])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int[] nk = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][] dp = new int[nk[0] + 1][nk[1] + 1];
        for (int i = 1; i < nk[0] + 1; i++) {
            int[] wv = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 1; j < nk[1] + 1; j++) {
                if (j < wv[0]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wv[0]] + wv[1]);
                }
            }
        }

        System.out.println(dp[nk[0]][nk[1]]);
    }
}