백준 12865 : 문제링크

  • 문제유형 :

    • 탐색

    • 동적 프로그래밍

  • 설명

    • 물품의 수 N, 배낭에 담을 수 있는 무게 K

    • 동적 프로그래밍을 이용하여 시간 복잡도(NK)

    • 핵심 아이디어: 모든 무게에 대하여 최대 가치를 저장하기

    • D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치

    • 각 물품의 번호 i에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결

    • 점화식
      스크린샷 2020-11-05 오후 9 09 54

    • N = 4, K = 7 일 때
      스크린샷 2020-11-05 오후 9 11 23

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    n, k = map(int, input().split())
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = map(int, input().split())
        for j in range(1, k + 1):
            if j < weight:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

    print(dp[n][k])