파이썬 알고리즘 077 | 가방문제(냅색 알고리즘)

77. 가방문제(냅색 알고리즘)

최고 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가치가 최대이다.

<내 풀이>

• dfs방식으로 풀어도 되나?..접근 방법을 모르겠다 냅색 알고리즘..

n, m= map(int, input().split())
w=[]
p=[]
k=[]
for i in range(n) :
    a,b=map(int,input().split())
    k.append((a,b))
k.sort()
for i in range(len(k)):
    w.append(k[i][0])
    p.append(k[i][1])
......모르겠어서 포기함

<풀이>

• dy는 m길이로 해준다 (가방에 담을 수 있는 무게의 값)
  dy[j]는 가방에 j라는 무게 까지 담는다 가정 시에 보석의 최대가치
• 우선 동적계획법은 작은 것에 집중해서 차근차근 보는 거니깐 5(w),12(v) 하나의 값만 있다고 가정하면
  dy[j-w] + v
  (j의 무게에서 보석의 무게 빼고 남은 공간 자리에서의 최댓값 + 가치)

n, m= map(int, input().split())
dy=[0]*(m+1)
for i in range(n) :
    w,v=map(int,input().split())
    for j in range(w,m+1) :#자신이 해당하는 무게에서부터 가방의 무게까지
        dy[j]=max(dy[j], dy[j-w]+v) #기존의 값 , j무게 가방에서 w만큼 뺀것에 가치를 더한 것
print(dy[m])
    

<반성점>

<배운 점>

링크텍스트

• 냅색알고리즘
  (ex) 한 가게에 도둑이 들었다. 도둑이 훔치고 싶은 물건들은 다 각각의 값어치와 무게가 있다.무게 때문에 도둑은 고를 수 있는 물건이 한정되어 있다.그러므로 가방에 다 담을 수 있는 내에서 가장 비싼 물건을 훔치고자 한다.
  =>동적 계획법(dynamic programming)을 사용합니다.
  dyn[i][j] = (가방의 크기가 i일때, j번째 물건까지 담을 수 있는 경우 최대 가치)라고 하면,
  dyn[0][i] = dyn[j][0]= 0 를 base case로 놓을 수 있다.
  그렇다면 점화식을 구해보자.
  i가 weight[j]보다 크거나 같으면 이 가방엔 이 물건이 들어갈 수 있다.
  그렇다면 j번째 물건을 넣는다고 가정했을 때,
  ((i-weight[j]) 크기의 가방에 (j-1) 번째 물건까지 넣을 수 있는 경우 최대 가치)에다가 value[j]를 더하는 모든 경우가 가능하다.
  어느 것이 최대인가는 경우에 따라 다르기 때문에 시도해봐야 한다.
  이 물건을 안 넣기로 하거나 가방 크기때문에 넣을 수 없다면,
  i번째 가방에 j-1번 물건을 넣을 수 있는 경우 최대 가치를 그대로 쓸 수 있다.

i≥weight[j]이면 dyn[i][j]=max(dyn[i][j-1],max(dyn[i-weight[j]][j]+value[j]))
i<weight[j]이면 dyn[i][j]=dyn[i][j-1]
이렇게 하면 답은 dyn[가방 크기][마지막 물건]

<2회독 내 풀이>

s=[]
n,m=map(int,input().split())
for i in range(n) :
    w, v = map(int,input().split())
    s.append((w,v))
dy=[0]*(m+1)

for i in range(n) :
    for j in range(s[i][0],m+1) :
        dy[j]=max(dy[j], dy[j-s[i][0]]+s[i][1])
print(max(dy))