파이썬 알고리즘-78 (DP) 가방문제(knapsack)

78.가방문제(냅색 알고리즘)
최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

▣ 입력설명
첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 두 번째 줄부터 각 보석의 무게와 가치가 주어진다.
가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

▣ 출력설명
첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

▣ 입력예제 1
4 11
5 12
3 8
6 14
4 8

▣ 출력예제 1
28

해설 : 5g 1개, 3g 2개를 선택해서 28가치가 최대이다.

내 코드

n,k=map(int,input().split())
lst=[tuple(map(int, input().split())) for _ in range(n)]

dy=[[0,0] for _ in range(n)]
dy[0]=[lst[0][0], lst[0][1]]

for i in range(1,n):
    p=0
    w=0
    for j in range(i-1,-1,-1):
        if lst[i][0]+dy[j][0]<=k and dy[j][1]>p:
            w=dy[j][0]
            p=dy[j][1]
    dy[i]=[lst[i][0]+w ,lst[i][1]+p]
print(dy)

이전에 풀던 방식으로 풀어보려 했지만 보석의 개수가 무한대라는 점을 해결할 수 없어 실패했다.

풀이

if __name__=="__main__":
    n, m=map(int, input().split())
    # 0~무게제한만큼의 리스트를 0으로 초기화
    dy=[0]*(m+1);
    # 보석의 종류만큼 반복문
    for i in range(n):
        # 보석의 무게와 가치를 각각 w,v에 할당
        w, v=map(int, input().split())
        # 보석의 무게부터 시작해서 무게제한까지 반복문
        for j in range(w, m+1):
            # 무게 w의 보석을 넣고 남는 공간이 있고, 그 공간을 채울 보석이 있다면 더해서 기존 dy[j]와 비교해서 큰 것을 넣는다
            dy[j]=max(dy[j], dy[j-w]+v)
    print(dy[m])

반성점

배운 것

• knapsack algorithm: 무게에 제한이 있는 가방이 존재하고, 그 안에 일정 무게와 가치를 지닌 물건을 넣었을 때 무게 제한을 넘지 않으면서 최대 가치를 가지도록 하는 알고리즘이다.