Untitled.py

# coding: utf-8

# 어떤 공장에서 생산하는 제품의 단위 및 출고가가 다음과 같다. 
# 
# * 1kg - 2
# * 4kg - 3
# * 10kg - 7
# 
# nkg을 출고하는데 드는 최소 비용과 이때의 생산량을 구해보자.

# n kg을 생산하는데 드는 최소출고가를 P(n) 이라 한다면
# 
# * P(n-1) + 2
# * P(n-4) + 3
# * P(n-10) + 7
# 
# 중 최소출고가가 P(n)이 될 수 있다. 
# 
# P(0) = 0 이 되므로 이는 재귀적으로 다음과 같이 뽑아 낼 수 있다. 


# In[71]:

table = {1:2, 4:3, 10:6}

def P(n):
    if n < 1:
        return 0
    f = [P(n-k) + v for k, v in table.items()]
    return min(f)

get_ipython().magic('time print(P(45))')


# 하지만 위에서 보듯이 목표값이 40을 넘어가는 순간부터 성능 문제가 크게 발생한다. (무려 12초나 걸렸다.)
# 그래서 캐싱을 한다.


# In[74]:
table = {1:2, 4:3, 10:6}

def memoize(f):
    cache = {}
    def wrapped(arg):
        if arg in cache:
            return cache[arg]
        r = f(arg)
        cache[arg] = r
        return r
    return wrapped

@memoize
def P2(n):
    if n < 1:
        return 0
    f = [P2(n-k) + v for k, v in table.items()]
    return min(f)

get_ipython().magic('time print(P2(45))')


# 캐싱을 하면 성능이 비약적으로 상승한다. 하지만 545를 목표값으로 정하면
# 이 계산은 실패한다. 왜냐하면 재귀의 양이 너무 많기 때문에 스택오버플로우가 일어나게 된다. 
# 
# 그래서 동적 프로그래핑을 적용해보기로 한다. 
# 
# 1. p[0] 은 0이다. 
# 2. 초기화되지 않은(그래서 값이 0인) 경우 p[n] 은 p[n-k]+v 가 된다. 
# 3. 0이 아닌 경우에는 p[n]은 p[n], p[n-k]]+v 중 작은값이 된다. 
# 

# In[78]:

table = {1:2, 4:3, 10:6}
target = 4585
prices = [0] + [0] * (target + 8)
for weight in table.keys():
    for i in range(weight, target+4):
        if prices[i] == 0:
            prices[i] = prices[i-weight] + table[weight]
        else:
            prices[i] = min(prices[i-weight] + table[weight],
                           prices[i])
get_ipython().magic('time print(prices[target:])')


# 위에서 보다시피 target값이 무식하게 늘어나더라도 계산시간은 "다차식"으로 늘어나므로 값이 클 수록 차이가 커진다.

# In[ ]: