백준 12865번: 평범한 배낭

문제

• https://www.acmicpc.net/problem/12865
• 동적 프로그래밍으로 부분집합을 효율적으로 탐색하기

기록 포인트

• 하위 문제로 분할하는 과정 (점화식을 만드는 과정)
• 탐색 범위를 좁힐 수 있도록 기록(memoization)할 대상을 선정하는 과정

접근 방식

• (아직 정리가 깔끔하지 못하니 전체적인 흐름만 참고해주세요!)

• 함수 fn의 정의

  • 입력: n개의 아이템, a_1, a_2, ... a_n
  • 출력: 입력 받은 아이템들로 구성 가능한 부분집합 중 '아이템 무게(w_i)의 합이 K보다 작거나 같다'는 조건을 충족하면서 '가치(v_i)의 합이 최대가 되는' 부분집합의 가치
  • 함수 구성

   def sum_weights(subset):
        return sum(item.w for item in subset)
        
    def sum_values(subset):
        return sub(item.v for item in subset)        
        
    def fn(items):
        subsets = combinations(items)
        max_value = 0
        for subset in subsets:
            if sum_weights(subset) <= K:
                max_value = max(max_value, sum_values(subset))
        return max_value

• 하위 문제(subproblem) 정의하기

  • 부분집합의 특성
    • 새로운 아이템(c)이 추가되면, 기존 부분집합들에 c를 넣은 부분집합들이 추가됨

  combinations([]) = [ [] ]
  combinations([a]) = [ [], [a] ]
  combinations([a,b]) = [ [], [a], [b], [a,b] ]
  combinations([a,b,c]) = [ [], [a], [b], [a,b], [c], [a,c], [b,c], [a,b,c] ]
                        = combinations([a,b]) + [subset + [c] for combinations([a,b])]

  • 하위문제를 포함하도록 함수 구성 (하향식)
    • 이 때, 무게의 합이 K보다 작아야 한다는 조건을 충족하는 부분집합만 추가

  # 각 아이템의 (무게, 가치)
  items = [(6, 13), (4, 8), (3, 6), (5, 12)] 
  
  def sum_weights(subset):
    return sum(item[0] for item in subset)
    
  def sum_values(subset):
    return sum(item[1] for item in subset)
    
  def fn2(items):
    # 종료 조건: 아이템이 없을 경우
    if len(items) == 0 :
        return 0, [[]]
    # 아이템이 존재할 경우, 아이템 하나를 제외한 아이템들로 하위 문제 구성
    item = items[0]
    prev_max, prev_subsets = fn2(items[1:])
    # 하위 문제의 부분집합들에 새로운 아이템을 추가해, 새로운 부분집합 생성
    new_subsets = []
    new_max = 0
    for s in prev_subsets:
        ns = s + [item]
        if sum_weights(ns) <= K:
            new_max = max(new_max, sum_values(ns))
            new_subsets.append(ns)
    max_value = max(new_max, prev_max)
    subsets = prev_subsets + new_subsets   
    return max_value, subsets
    
  max_value, subsets = fn2(items)
  print(max_value)

  • 정보 축소 및 상향식으로 재구성
    • 본 문제는 부분집합을 재구성할 필요는 없으므로 기존에 부분집합을 보관하던 subsets을, 답이 될 가능성이 있는 부분집합의 (무게합, 가치합)을 보관하는 candidates로 변경
    • (이 답안까지 시간초과 발생)

    candidates = [(0,0)]
    max_value = 0
    for w, value in items:
        new_candidates = []
        for prev_w, prev_value in candidates:
            new_w = prev_w + w
            new_value = prev_value + value
            if new_w <= K:
                new_candidates.append((new_w, new_value))
                max_value = max(max_value, new_value)
        candidates = candidates + new_candidates
  
    print(max_value)

  • 중복되는 탐색 범위 제외 (중복되는 부분 문제 처리)

    • 무게합이 동일한 두 부분집합 A, B가 있을 때, A의 가치합이 B의 가치합보다 작으면, A를 포함하는 부분집합의 가치합은 B를 포함하는 부분집합의 가치합보다 항상 작을 수밖에 없음
    • 그러므로 답이 될 가능성이 있는 부분집합 중 무게합이 동일한 부분집합이 있으면, 가치합이 큰 부분집합만 보관하면 됨
    • 결과적으로 각 아이템이 추가될 때마다 고려해야하는 선택지가 1~K로 줄어듦
      • 각 선택지가 의미하는 바는, '무게합인 w인 이전의 조합'
      • 즉, 이전 아이템까지 활용해 만든 조합 중 '무게합이 w인 조합'들이 있었는데 '그 조합들의 가치합 중 최대값은 value'
      • 그러므로 각 선택지에서 하는 행위는, 기존의 조합에 새로운 아이템을 추가해 무게의 변화와 가치 변화를 확인하는 것

   # 답이 될 수 있는 조합들에서 동일 무게 중 가치가 최대인 조합만 남김
   # 동일 무게 중 가치가 작은 조합은, 동일 무게 중 가치가 큰 조합보다 더 좋은 조합을 만들 수 없기 때문
   # candidates는 각 무게에서 최대의 가치를 저장
  candidates = {0: 0}
  for w, value in items:
      new_candidates = dict(candidates)
      for prev_w, prev_value in candidates.items():
          new_w = prev_w + w
          new_value = prev_value + value
          if new_w <= K:
              if new_w not in candidates or candidates[new_w] < new_value:
                  new_candidates[new_w] = new_value
      candidates = new_candidates
  
   print(max(candidates.values()))

제출 답안

import sys

N, K = tuple(map(int, sys.stdin.readline().split()))
items = []
for _ in range(N):
    w, value = tuple(map(int, sys.stdin.readline().split()))
    items.append((w, value))

candidates = {0: 0}
for w, value in items:
    new_candidates = dict(candidates)
    for prev_w, prev_value in candidates.items():
        new_w = prev_w + w
        new_value = prev_value + value
        if new_w <= K:
            if new_w not in candidates or candidates[new_w] < new_value:
                new_candidates[new_w] = new_value
    candidates = new_candidates

print(max(candidates.values()))