Part7.10_동적프로그래밍(DynamicProgramming)_동전교환(냅색 알고리즘)

문제

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.

출력

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

정답 풀이

• 냅색 알고리즘을 이용한다.
  냅색 알고리즘은 참 재밌는거 같다

정답 코드

import sys
sys.stdin = open ("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    coin = list(map(int,input().split()))
    m = int(input())
    dy=[1000]*(m+1)
    dy[0]=0

    for i in range(n):
        for j in range(coin[i], m+1):
            dy[j] = min(dy[j], dy[j-coin[i]]+1)
    print(dy[m])

코멘트

냅색 알고리즘 설명
냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다.

담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)

담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)

해당 문제는 0-1 배낭문제의 경우다.

이 문제는 다음과 같은 알고리즘으로 풀 수 있다. 풀어서 한 번, 식으로 한 번 설명하겠다.

알고리즘
1) x축엔 가방 1~K 까지의 무게, y축은 물건 N개 개수 만큼의 배열을 만들어준다.

2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.

3-0) 현재 물건이 현재 돌고있는 무게보다 작다면 바로 [이전 물건][같은 무게] (knapsack[i-1][j]를 입력해준다.

3-1) 현재 물건을 넣어준다. 물건을 넣은 뒤의 남은 무게를 채울 수 있는 최댓값(knapsack[i-1][j-weight]을 위의 행에서 가져와 더해준다.

3-2) 현재 물건을 넣어주는 것보다. 다른 물건들로 채우는 값(knapsack[i-1][j])을 가져온다.

4) 3-1과 3-2 중 더 큰 값을 knapsack[i][j]에 저장해준다. 이 값은 현재까지의 물건들로 구성할 수 있는 가장 가치 높은 구성이다.

5) knapsack[N][K]는 곧, K무게일 때의 최댓값을 가리킨다.

수식
결국 수식으로 표현하면 다음과 같다.

knapsack[i][j] = max(현재 물건 가치 + knapsack[이전 물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전 물건][현재 가방 무게])

knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

결국 아래와 같은 엑셀이 만들어진다.