12868_평범한 배낭

문제는 더보기!

 

문제

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

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

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

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

출력

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

예제 입력 1 복사

4 7
6 13
4 8
3 6
5 12

예제 출력 1 복사

14

 

 

 

어려웠다... 차근차근 이해해보자

 

먼저 item이란 배열을 만들어서

[[0, 0], [6, 13], [4, 8], [3, 6], [5, 12]]

위와 같은 값을 저장해준다.

 

그다음에 2차원 배열을 하나만들어서 세로축엔 item의 index값이 ( 물건들을 하나씩 ) 가로축엔 무게를 1씩 증가시키게 두었다고 생각할 것이다.

 

 

동적계획법의 여느 풀이처럼 물건을 하나씩 추가시키면서 배열을 채워나갈껀데, 하나씩 채울때 무게를 0부터 허용범위 무게까지 검사하는것이다. 어떻게 보면 동적 계획법 풀이를 2번 적용시킨것과 같다.

 

[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 13, 13]
[0, 0, 0, 0, 8, 8, 13, 13]
[0, 0, 0, 6, 8, 8, 13, 14]
[0, 0, 0, 6, 8, 12, 13, 14]

 

우선 결과는 위처럼 나오게 된다. 그럼 가로축을 채울때 어떻게 채울지 생각해보자.

 

우선 [3,6] 의 물건을 가진 값을 가진다고 생각해보자. 만약 3보다 가벼운 무게라면 가방에 물건을 넣을 수 없으므로 이 물건을 넣기 전의 단계의 값을 그대로 가져오면 된다.

 

즉, result[i][j] = result[i-1][j]

 

 

3보다 무거울 경우에는 비교를 해야한다..! [3,6]은 3번째로 넣은 물건이다. 무게가 6인 부분을 계산해본다 생각해보자.

 

이때 2번째로 넣은 물건의 무게가 6인부분의 값(13) 과 현재 [3,6]을 넣었다고 가정해서 2번째로 넣은 물건의 무게가 6-3 즉 3인 부분의 값(0) 에 현재 물건의 가치를 더한 6 중에서 비교를 하면된다.

 

result[i][j] = max(result[i-1][j],result[i-1][j-item[i][0]] + item[i][1])

 

식으로는 위와같다.

 

설명만 보면 살짝 어려울 수 있는데, 코드를 돌려보면서 result값과 item값을 출력해보면 이해하기 수월할 것이다.

 

import sys
n,k = map(int, sys.stdin.readline().split())

item = [[0,0]]
for i in range(1,n+1):
    item.append(list(map(int,sys.stdin.readline().split())))
result = [ [0]  * (k + 1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        if j >= item[i][0]:
            result[i][j] = max(result[i-1][j],result[i-1][j-item[i][0]] + item[i][1])
        else :
            result[i][j] = result[i-1][j]

print(result[-1][-1])

print(item)
for i in result:
    print(i)