[백준] 12865 평범한 배낭 (파이썬)

문제링크

문제

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

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

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이

1kg,2kg ...7kg 가방에 1번 물건만 존재할때

1번 물건은 3kg이므로 3kg 이상인 가방에만 들어갈 수 있습니다.
li[j][i] = wv[j-1][1]

1,2번 물건이 존재할때 2번물건은 5kg이상인 가방에 들어갈 수 있습니다. 하지만 5kg가방안에는 3kg의 물건이 들어있고 5kg물건의 가치가 3kg에 비해 높으므로 5kg의 물건이 들어가야합니다.
li[j][i] = max(li[j-1][i], wv[j-1][1])

6kg의 가방에 1번물건과 2번물건을 가지고 최대 가치를 만든다면 이미 넣은 1번 물건의 가치보다 2번 물건의 가치가 더 높으므로 2번 물건을 넣어야 합니다.
하지만 2번 물건을 넣고나면 6kg-5kg=1kg이 남게 됩니다. 현재 표에서는 1kg의 최대치가 0 이므로 5kg물건의 가치인 12가 그대로 6kg가방의 가치가 되지만 1kg의 최대가치가 존재한다면 해당 가치를 더해주는게 6kg의 가치가 될 것입니다.

3번물건을 6kg가방에 넣는다면 3kg이 남게됩니다. 3번물건을 제외한 3kg의 최대값과 3번물건의 가치를 더한값이 이전 6kg의 최대값보다 크기 때문에 6kg의 가치는 14가 됩니다.
li[j][i] = max(wv[j-1][1] + li[j-1][i-wv[j-1][0]],li[j-1][i]

코드

n, k = map(int,input().split())
wv = []

for i in range(n):
    w,v = map(int,input().split())
    wv.append([w,v])

wv.sort() # 없어도 됩니다. 보기 편할려고 넣었어요

li=[[0] * (k + 1) for _ in range(n+1)] # 최대값을 비교하기위한 표 생성

for j in range(1,n+1): # 물건의 개수
    for i in range(1,k+1): # 배낭의 무게(1kg일때, 2kg일때 ~~ 7kg일때 )
        if wv[j-1][0]<= i: # 배낭의 무게보다 물건의 무게가 작을때
            li[j][i] = max(wv[j-1][1] + li[j-1][i-wv[j-1][0]],li[j-1][i])
        else:
            li[j][i] = li[j-1][i] # 배낭의 무게가 물건의 무게보다 크면 이전물건까지 넣었을때의 최대가치가 들어간다
print(li[n][k])