백준 - 12865 평범한 배낭 [DP][탑다운][바텀업]

 

12865번: 평범한 배낭

 

1. 문제 요약

물품의 수 N, 버틸 수 있는 무게 K, 각 물건의 무게 W, 물건의 가치 V가 주어집니다.

물건들을 가장 많이 가져갈 수 있는 조합을 구하시오.

 

2. 접근 방법

먼저 완전탐색으로 모든 경우의 수를 다 때려 넣어봅니다.

def solution(idx, w, v):
    global answer
    if w > K:
        return
    if idx == N:
        answer = max(answer, v)
        return
    
    solution(idx+1, w+items[idx][0], v+items[idx][1])
    solution(idx+1, w, v)

 

시간과 메모리가 충분하다는 가정하에 해결할 수 있지만, 해당 문제는 시간초과가 발생하므로 최적화를 진행해야 합니다.

 

위 풀이를 살짝만 수정해 주면 탑다운 DP방식으로 전환할 수 있습니다.

가장 뒤에서부터 이전 방법과 비교하여 더 큰 값을 기록하는 방식을 사용합니다.

 

탑다운 방식에서 다시 수정하여 일반적으로 잘 알려진 방식인 바텀업 방식으로 변경해 보겠습니다.

 

3. 파이썬 (탑다운)

dp = [[-1] * (K+1) for _ in range(N)]

def solution(idx,w):
    if w > K:
        return -1e9
    if idx == N:
        return 0
    if dp[idx][w] != -1: # 방문했는지 여부를 확인하는 핵심 부분
        return dp[idx][w]
    
    dp[idx][w] = max(
        solution(idx+1,w+items[idx][0]) + items[idx][1], # 사용하거나
        solution(idx+1,w) # 사용하지 않거나
    )

    return dp[idx][w]

 

4. 자바 (바텀업)

static private int solution(int n, int k, int[][] items) {
    int[][] dp = new int[n + 1][k + 1];

    for (int index = 1; index <= n; index++) {
        for (int weight = 1; weight <= k; weight++) {

            if (weight < items[index - 1][0]) { // 무게 체크하는 부분 (위 코드에서 if문 부분)
                dp[index][weight] = dp[index - 1][weight];
            } else {
                dp[index][weight] = Math.max(
                        dp[index - 1][weight], // 사용하지 않거나
                        dp[index - 1][weight - items[index - 1][0]] + items[index - 1][1] // 사용하거나
                );
            }

        }
    }

    return dp[n][k];
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/12865.%E2%80%85%ED%8F%89%EB%B2%94%ED%95%9C%E2%80%85%EB%B0%B0%EB%82%AD