백준 / 평범한 배낭 / 12865번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 평범한 배낭 / 12865번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/12865

 

문제 설명

---

나의 풀이

# bp는 배낭을 의미, k는 준서가 담을 수 있는 무게
def solution(bp, k):
    # 가장 가치가 높을 때
    max_value = 0

    # 가방에서 무게는 오름차순 가치는 내림차순으로 정렬
    bp.sort(key=lambda x: (x[0], -x[1]))

    for i in range(0, len(bp)):
        current_weight = bp[i][0]
        current_value = bp[i][1]

        for j in range(i + 1, len(bp)):
            next_weight = bp[j][0]
            next_value = bp[j][1]
            if current_weight + next_weight <= k:
                current_weight += next_weight
                current_value += next_value
            else:
                max_value = max(max_value, current_value)
                break

    return max_value

N, K = map(int, input().split())

backpack = [list(map(int, input().split())) for _ in range(N)]

print(solution(backpack, K))

이 풀이의 문제는 0-1 배낭 문제의 기본적인 요구 사항을 충족하지 못하고, 몇 가지 중요한 오류가 있다.

1. 그리디 알고리즘으로 정확하게 풀 수 없다.

2. 모든 경우의 수를 고려하지 않는다(각 물건을 넣거나 넣지 않는 두 가지 선택지를 모두 고려해야 하지만 위 풀이는 그걸 고려하지 않음)

3. max_value 부분에서는 최대값이 나오면 즉시 갱신하고 반복문이 종료된다. 이렇게 되면 두 개의 사물만 비교하게 된다.

 

 

그래서 이 문제는 DP를 이용해서 해결해야한다.

def solution(bp, k):
    # dp[i]는 무게가 i일 때 최대 가치
    dp = [0] * (k + 1)

    # 각 물건에 대해
    for weight, value in bp:
        # 현재 배낭 용량에서 물건을 넣었을 때의 가치를 갱신
        for i in range(k, weight - 1, -1):
            dp[i] = max(dp[i], dp[i - weight] + value)

    # dp[k]에 저장된 값이 최대 가치
    return dp[k]

N, K = map(int, input().split())

backpack = [list(map(int, input().split())) for _ in range(N)]

print(solution(backpack, K))

"""
예제
4 7
6 13
4 8
3 6
5 12

결과
7 : 13 6 : 13 
7 : 13 6 : 13 5 : 8 4 : 8 
7 : 14 6 : 13 5 : 8 4 : 8 3 : 6 
7 : 14 6 : 13 5 : 12 
14
"""

"결과"의 코드는 따로 넣지는 않았기만 문제를 이해하기 위해서 따로 넣어서 결과물을 출력했다.

이렇게 코드를 짜면 k일 때 최대 가치를 뽑을 수 있다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/175

[Algorithm] 동적계획법(Dynamic Programming)