냅색 알고리즘 _ 가방문제, 동전교환, 최대 점수 구하기

 

 

스터디는 이미 끝났지만 

이미 구매해놓은 인강 다 듣고 풀어야지..

 

 

----

🐾20220914 복습 

 

 

어떻게 풀 때마다 까먹지...?

그래도 처음 봤을 때 보다 더 빨리 풀었다는 것에 의의를 둔다...

 

 

가방 문제 : 

if __name__=="__main__" :
    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-w] + v, dy[j])
    print(dy[m])

 

weight 와 value가 주어질 때 주어진 무게까지 담을 수 있는 가방에서 최대의 가치를 만들어라 

 

 

dy[j] 의 의미 :  j 무게까지 담길 때의 최대 가치를 의미한다. 

 

n번 보석들의 무게와 가치를 입력받고 

w ~ m 까지 j로 돌면서 

dy의 값들이 최대가치를 가지도록 갱신해준다. 

 

 

dy[j] = max(dy[j-w] + v, dy[j]) 

dy[j-w] + v 는 가방에서 w 만큼 보석을 넣기전 가치에서 w 무게의 보석을 넣을 때의 최대가치를 의미한다.

이 값과 기본 값을 비교하여 최댓값으로 갱신해준다. 

 

 

 

 

동전 교환 : 

if __name__=="__main__" :
    n = int(input())
    coin = list(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-coin[i]] +1 , dy[j])
    print(dy[m])

 

dy[j] 의 의미는 j 원을 만드는 동전의 최소개수이다. 

동전의 단위를 coin 리스트를 만들어 입력받는다. 

 

dy[j] = min(dy[j - coin[i]]+1 , dy[j]) 

동전을 돌면서 (해당 동전의 값을 뺀 값을 만드는 동전의 개수 + 1 )[현재 동전을 하나 채움]과 기존의 있던 개수 중 작은 값으로 값을 갱신한다. 

 

 

 

 

최대 점수 구하기  :

if __name__=="__main__" :
    n,m = map(int,input().split())
    dy = [0]*(m+1)
    for i in range(n) :
        s,t = map(int,input().split())
        for j in range(m, t-1, -1 ) :
            dy[j] = max(dy[j-t]+s, dy[j])
    print(dy[m])

 

dp[i] : i시간 안에 푼 문제의 최대 점수   

 

 

이전에 풀었던 문제와는 다르게 

유형당 문제가 하나 뿐이다. 그래서 t부터 m까지 가는것이 아니라

m부터 t까지 거꾸로 탐색하면서 유형당 한 문제만 풀 수 있게 만들어야한다. 

 

 

<미리 한번에 받는 코드> 

if __name__=="__main__" :
    n,time = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(n)]
    dp = [0]*(time+1)
    
    for i in range(n) :
        for j in range(time, arr[i][1]-1, -1) :
            dp[j] = max(dp[j-arr[i][1]] + arr[i][0], dp[j])
    print(dp[time])