냅색 알고리즘 (Knapsack Problem)

배낭문제(Knapsack Problem)

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다.


배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데,

• 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem)
• 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)
  0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다.

문제1 > 배낭문제 (inflearn) / 보석개수 무한

구현 방법

• d[j] :가방의 무게가 j일 때, 최대 가치의 값

• d[j] = max( d[j-w]+v , d[j] )
  가방에 w의 무게의 물건이 담겼을 때와, 안담겼을 때를 비교하여 최대 가치의 값을 담아줌.

구현코드

# n : 물건의 수 / k : 무게 제한
n, k = map(int, input().split())
d = [0]*(k+1)

for _ in range(n):
    w,v = map(int,input().split())
    for j in range(w,k+1):
        d[j] = max(d[j], d[j-w]+v)
print(d[k])

문제2 > 백준.12865 평범한배낭

구현방법

• 위의 문제 1과 동일하나, 위의 문제는 보석의 개수를 무한개로 사용이 가능하고, 현재 평범한 배낭 문제는 문제의 조건에서는 찾아볼 수 없으나 1개만 담을 수 있는듯 하다...
  >> 이와 같이 개수가 한정된 경우는 dp 배열을 돌 때 뒤에서부터 체크해줘야 한다!

구현코드

# n : 물건의 수 / k : 무게 제한
n, k = map(int, input().split())
d = [0]*(k+1) #인덱스번호 k까지

for _ in range(n):
    w,v = map(int,input().split())
    for j in range(k,w-1,-1):
        d[j] = max(d[j], d[j-w]+v)
print(d[k])

냅색알고리즘 풀 때 주의사항!!🌟

1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터.
2. 개수가 정해져있을때, 종류마다 한개씩 존재, 유한개면 뒤에서부터.