[백준] 12865 평범한 배낭(파이썬) - 냅색 알고리즘

 

 

알고리즘

배낭의 최대가치를 결정하는 과정은 크게 두 가지의 경우로 생각할 수 있다.

1. 배낭의 무게보다 물건의 무게가 더 크면 물건을 넣지 않는다.
2. 그렇지 않다면 배낭의 가치를 측정한다.
   • (이전 물건이 있으면 전부 빼고) 새로운 물건을 넣는다. 그리고 배낭의 무게에서 새로운 물건의 무게를 뺐을 때의 배낭의 최대 가치를 고려한다.
   • 새로운 물건을 넣지 않고 이전 배낭을 그대로 가져간다.

어떤 자료구조를 사용해야 할까?

 일단, 배낭에 물건을 넣거나 빼면서 배낭의 최대가치를 결정해야 하므로 각 물건의 무게와 가치를 저장할 2차원 배열이 필요하다.

i \ j	0	1
0	a의 무게	a의 가치
1	b의 무게	b의 가치
2	c의 무게	c의 가치

이를 obj[i][j]로 정의하겠다.

 

그리고 배낭의 무게와 물건에 따른 배낭의 가치를 계산해야할 필요가 있으므로 물건과 배낭 무게를 변수로 하여 배낭의 최대 가치를 저장할 2차원 배열이 필요하다.

i \ j	0	1
0	0	?
1	0	?
2	0	?

이를 v[i][j]로 정의하자. (i번째 물건을 넣을 때 무게가 j인 배낭의 최대가치)

따라서 우리가 출력할 값은 무게가 K인 배낭에서 N번째 물건까지 고려했을때의 최대 가치인 v[n][k]이다.

 

위의 내용을 바탕으로 알고리즘을 코드로 생각해 본다면 아래와 같다.

1. k < weight : v[n][k] = d[n-1][k]
2. v[n][k] = max( d[n-1][ k-weight ]+value , d[n-1][k] )

weight은 n번째 물건의 무게인 obj[n][0]이고, value는 n번째 물건의 가치인 obj[n][1]로 정의된다.

 

이해를 위해 v[4][7]의 값을 도출하는 과정을 생각해보자. 입력 값은 백준 12865번을 그대로 사용한다.

▶ v[1][7] = 13

첫번째 물건을 배낭에 담는다.

▶ v[2][7] = max( 13, v[1][7-4] + 8 ) = max(13, 8) = 13

2번째 물건을 담지않고 기존의 배낭을 그대로 유지한다.

▶ v[3][7] = max( 13, v[2][7-3] + 6 ) = max(13, 14) = 14

3번째 물건을 담고, 2번째 물건까지 고려했을때 무게가 4인 배낭의 최대가치를 더한 값이 v[3][7]이 된다.

▶ v[4][7] = max( 14, v[3][7-5] + 12 ) = max(14, 12) = 14

4번째 물건을 담지않고, 기존의 배낭을 그대로 유지한다.

 

 

전체 코드

n ,k = map(int, input().split())

#배열에 물건의 무게와 가치 초기화
obj=[[0,0]] #인덱싱을 1부터 하기위함

for _ in range(n):
     obj.append(list(map(int, input().split())))

#배낭의 최대가치 배열 초기화
v = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        weight = obj[i][0] 
        value = obj[i][1]

        if(weight>j):
            v[i][j] = v[i-1][j]
        else:
            v[i][j] = max(v[i-1][j-weight]+value, v[i-1][j])

print(v[n][k])

 

 

코드 참고

https://claude-u.tistory.com/208

#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘