[Baekjoon] # 12865: 평범한 배낭

평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 
세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 
가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 
각 물건은 무게 W와 가치 V를 가지는데, 
해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 

아직 행군을 해본 적이 없는 준서는 
최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 
준서가 최대한 즐거운 여행을 하기 위해 
배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

예제

• 입력

  4 7
  6 13
  4 8
  3 6
  5 12
  

• 출력

  14
  

  ---

Solution

def get_inputs():
    import sys

    input_data = sys.stdin.read()
    inputs = input_data.splitlines()

    str_to_int_arr = lambda x: list(map(int, x.split()))

    item_count, max_weight = map(int, inputs[0].split())
    data = list(map(str_to_int_arr, inputs[1:]))

    return item_count, max_weight, data


def solution():
    item_count, max_weight, data = get_inputs()

    if item_count == 1:
        return data[0][1] if data[0][0] <= max_weight else 0

    value_table = [0] * (max_weight + 1)

    for i in range(item_count):
        weight, value = data[i]

        if weight > max_weight:
            continue

        for looping_weight in range(max_weight, 0, -1):
            if (
                looping_weight + weight <= max_weight
                and value_table[looping_weight] != 0
            ):
                value_table[looping_weight + weight] = max(
                    value_table[looping_weight + weight],
                    value_table[looping_weight] + value,
                )

        value_table[weight] = max(value_table[weight], value)

    return max(value_table)


def main():
    print(solution())


if __name__ == "__main__":
    main()

---

해결 방법

---

Dynamic Programming을 활용

• 입력 예제의 물건들을 순서대로 A, B, C, D라고 하자
• 최대 7 Kg를 가지는 가장 높은 Value를 가지는 조합을 찾자

1. 하위 문제 정의
   • 각 물건을 넣을지 말지 결정하는 하위 문제를 정의
   • 즉, A를 넣는 것(1) 또는 넣지 않는 것(0)으로 시작
2. 결과 계산
   • 가능한 모든 조합을 고려하지만, 이전에 확인된 조합 중에서 무게를 초과하는 것은 무시
     1. 먼저 넣은 물건들의 무게를 더함
     2. 최대 무게가 넘지 않는다면 무게를 저장

• 동적 프로그래밍을 사용하여 해결하기 위해, 아래와 같은 테이블을 사용

동적 프로그래밍 테이블

• 무게의 최대 Value를 저장하는 테이블을 0으로 초기화
• 순서대로 물건을 넣는다고 가정
• 모든 조합을 고려하여 Value의 최대값을 계산

무게(w)	A (6kg, 13)	B (4kg, 8)	C (3kg, 6)	D (5kg, 12)
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5	0	0	0	12
6	13	13	13	13
7	0	0	14	14

• 마지막 열의 최댓값인 14가 가질 수 있는 최대 Value이다.

---

주의 사항

탑다운 방식으로 구현한 이유

• 중복 계산이 되는 문제가 발생
  • 1 Kg, 4 value를 넣고 2 Kg, 5 value를 넣는다고 가정
  1. 3 kg의 max_value는 4 + 5 = 9가 됨
  2. 3 Kg의 물건이 없다면, 5 kg의 max_value가 0이 되어야 함
     • 즉, 3 Kg의 max_value가 0이었다면 5 kg의 max_value가 0이 되어야 함
  3. 하지만 3 Kg의 max_value가 9 로 계산이 되었으므로, 5 Kg의 max_value가 $4 +5 = 9$이 됨

---

의사 코드

함수 solution():
    value_table을 크기 (max_weight + 1)로 초기화하고 모든 요소를 0으로 설정

    각 아이템 i에 대해 (data의 각 항목에 대해):
        weight = data[i][0]
        value = data[i][1]

        만약 weight가 max_weight보다 크다면:
            다음 아이템으로 건너뜀

        looping_weight를 max_weight에서 1까지 감소시키며 반복: ## 탑다운 방식
            
            만약 looping_weight + weight가 max_weight 이하이고,
            value_table[looping_weight]이 0이 아니라면:
            
                value_table[looping_weight + weight]을 다음 중 큰 값으로 업데이트:
                    - value_table[looping_weight + weight]
                    - value_table[looping_weight] + value

        value_table[weight]을 다음 중 큰 값으로 업데이트:
            - value_table[weight]
            - value

    value_table에서 최대 값을 반환

---

URL

• 평범한 배낭