[ 백준 12865번 ] 아주 평범한 배낭 파이썬

[백준 12865번 바로가기]

12865번: 평범한 배낭

논리

1. 배낭의 한계 무게에서 가질 수 있는 물건들의 가치의 최대값
2. 각 무게마다의 최대 가치를 가지는 table을 만든다(table[i]: i무게에서 가질 수 있는 최대값)
3. 각 물건마다 table[i]에 들어가는 경우를 생각해보고 가치의 최댓값을 갱신한다
4. ex) 한 물건으 무게가 w, 가치가 v라고 할 때, table[i]에서 이 물건을 고려해보자 --> i무게에서 w만큼 뺐을 때의 최대 가치에서 v를 더한 것이랑 비교 --> table[i] = max(table[i], table[i-w] + v)를 각 물건마다 한다
5. 이때 물건은 한번밖에 사용 못하므로 i: w to max_weight이 아니라 i: max_weight to w의 방향으로 한다(동전 최소 사용하기 문제랑 반대)

코드

import sys


def max_value():

    # inputs
    N, K = map(int, sys.stdin.readline().split())
    items = []  # [[weight1, value1], .. , [weightN, valueN]]
    for _ in range(N):
        weight, value = map(int, sys.stdin.readline().split())
        items.append([weight, value])


    table = [0] * (K + 1)   # table[i]: largest value of k weight

    # 각 물건마다 고려한다
    for weight, value in items:
        # 각 무게마다 물건의 무게를 뺀 만큼의 가치에서 물건의 가치를 더한 것과 비교
        # 물건을 하나만 쓸 수 있으므로 역순으로 비교
        for target in range(K, weight-1, -1):
            table[target] = max(table[target], table[target-weight] + value)

    print(table[-1])

max_value()