0413

다이나믹 프로그래밍

동적

 

 

# Problem 1. 
#  You are given array and goal variables. You have to find if there exists any subset that will sum equal to 'goal'.

def subsetSum(array, goal):
    n = len(array) 
    dp = [[0]*(goal+1) for _ in range(n+1)] 

    # dp array is initialized. 
    # The number of elements is greater than 0. 
    # The value of 'goal' can be 0 
    for i in range(goal+1):
        dp[0][i] = False
    for j in range(n+1):
        dp[j][0] = True

    # An element can be chosen only if sum is less han arr[i] else it cannot be included
    # Please fix your code below 
    for i in range(1,n+1):
        for j in range(goal+1):
            if array[i-1] <= j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j - array[i-1]]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][goal]


if __name__ == '__main__':
    array = [0, 3, 2, 7, 1]
    solution = subsetSum(array, 0)
    assert(solution==True)
    solution = subsetSum(array, 1)
    assert(solution==True)
    solution = subsetSum(array, 2)
    assert(solution==True)
    solution = subsetSum(array, 3)
    assert(solution==True)
    solution = subsetSum(array, 6)
    assert(solution==True)
    solution = subsetSum(array, 13)
    assert(solution==True)
    solution = subsetSum(array, 20)
    assert(solution==False)
    solution = subsetSum(array, 100)
    assert(solution==False)

    # An element can be chosen only if sum is less han arr[i] else it cannot be included
    # Please fix your code below 
    for i in range(1,n+1):
        for j in range(goal+1):
            if array[i-1] <= j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j - array[i-1]]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][goal]

중요한건 for에 있는 부분

 

dp[i][j] = dp[i-1][j] or dp[i-1][j - array[i-1]]  <<< 이 부분

 

dp[i][j] -> 지금 체크 하려는것(j로 만들수 있는가)

dp[i-1][j] -> 지금 넣으려는 거 안넣고 j가 만들어졌는가(array[i-1])

dp[i-1][j - array[i-1]] -> 지금 넣으려는거 넣고 j - array[i - 1]이 만들어 졌는가

 

 

 

# Problem 3
# Given an array of available denominations of coin and one target price. 
# Find the minimum number of coins required to pay the same.

import sys
def minCoins(coins, price):
    n = len(coins)
    # define dp array
    dp  = [[0]*(price+1) for _ in range(n+1)]

    # DP array is initialized 
    # If price = 0 then min coins needed = 0 considering null set. So dp[i][0] = 0.
    # If no. of coins = 0 then we would need infinite coins to get to price. So dp[0][j] = inf -1 ("-1 to avoid overflow)

    for j in range(price+1):
        dp[0][j] = sys.maxsize -1
    for i in range(n+1):
        dp[i][0] = 0

    # A coin can be selected only if its value is less than required price
    # Please fix your code below 
    for i in range(1,n+1):
        for j in range(1,price+1):
            if coins[i - 1] <= j:
                dp[i][j] = min(dp[i][j-coins[i-1]] + 1, dp[i-1][j]);
            else:
                dp[i][j] = dp[i-1][j];

    return dp[n][price]



if __name__ == '__main__':
    coins = [1, 5, 10]; price = 0
    ch = minCoins(coins,price)
    print(f'Minimum number of coins required : {ch}')
    assert(ch==0)
    coins = [1, 5, 10]; price = 1
    ch = minCoins(coins,price)
    print(f'Minimum number of coins required : {ch}')
    assert(ch==1)
    coins = [1, 5, 10]; price = 7
    ch = minCoins(coins,price)
    print(f'Minimum number of coins required : {ch}')
    assert(ch==3)
    coins = [1, 5, 10]; price = 20
    ch = minCoins(coins,price)
    print(f'Minimum number of coins required : {ch}')
    assert(ch==2)
    coins = [1, 5, 10]; price = 100
    ch = minCoins(coins,price)
    print(f'Minimum number of coins required : {ch}')
    assert(ch==10)

얘도 마찬가지
dp[i][j] -> 지금 구하려는거 (j까지 만드는데에 코인 몇개 썼는가)

dp[i][j-coins[i-1]] + 1  -> 지금 넣으려는 코인(coin[i-1])을 넣고 j값을 만드는데 사용한 코인 수

dp[i-1][j] -> 지금 넣으려는 코인을 넣지 않고 j값을 만드는데 사용한 코인 수