[알고리즘] 평범한 배낭

평범한 배낭 문제

---

분석

첫 줄에는 물건의 개수 n, 배낭에 넣는 물건의 최대 무게 k
다음 줄부터는 n줄만큼 물건의 무게, 가치가 입력된다.

4 7
6 13
4 8
3 6
5 12

냅색 알고리즘을 활용하여 풀어보았다.

---

냅색 알고리즘

무게별로 최대의 가치를 저장할 수 있는 0으로 초기화된 dy 리스트를 만든다.

입력받은 물건의 개수만큼 반복하여 각 무게별로 물건을 넣었을때 가치를 비교하여 더 높은 가치의 값을 저장한다.
첫번째 물건을 넣었을때 가치를 저장하고 두번째 물건을 넣었을때 6의 무게에서 첫번째 물건보다 두번째 물건을 넣을때가 더 높기 때문에 값을 바꾼다. 이 과정을 반복하면 제한 무게들 중에 최대 가치를 찾을 수 있다.

for i in lists:
    for j in range(i[0],k+1):
        dy[j] = max(dy[j], dy[j-i[0]]+i[1])

넣을 수 있는 물건이 하나

위의 알고리즘에는 문제가 있다.
물건이 여러개인 경우에만 적용된다
제한 무게가 7이고 무게가 3인 경우 무게 6에서 같은 물건이 2개가 들어간 경우가 나온다.
이를 해결하기 위해서는 무게를 앞에서부터 확인하지 않고 뒤에서 부터 확인하면 앞의 무게가 적용되지 않기 때문에 이를 해결할 수 있다.

for i in lists:
    for j in range(k,i[0]-1,-1):
        dy[j] = max(dy[j], dy[j-i[0]]+i[1])

---

코드

# 입력 받기
n, k = map(int, input().split())
lists = [list(map(int,input().split())) for _ in range(n)]

# 리스트 만들기 
dy = [0]*(k+1)

# 계산 
for i in lists:
    for j in range(k,i[0]-1,-1):
        dy[j] = max(dy[j], dy[j-i[0]]+i[1])
print(max(dy))