[アルゴリズムパターン]動的プログラミング-2

29726 ワード
せつぞくせん アルゴリズム#アルゴリズム# テキストリンク
Code Eatアルゴリズムのクラシックコースのコースまとめ.
不正確な内容や漏れがある場合がありますので、講義をお勧めします.
前の文章ダイナミックプログラミングとテクニックを理解しました.(Memoization, Tabulation)
この文章では,各方法の長所と短所を比較し,より深い問題を解決し,まとめた.

8. Memoization vs Tabulation


共通点


MemoizationとTabulationは、重複する問題の非効率性を解消します.

差異

  • Memoizationは再帰関数を使用し、Tabulationは重複文を使用します.
  • 再コールの場合、コールスタックは蓄積される.Call Stackの容量が限られている場合は、Tabulationが適切である可能性があります.
  • Tabulationは最初から計算します.いらなくてもいいです.Memoizationはトップダウンで必要な計算のみを実行します.

    • 9.動的計画空間の最適化

  • Tabulationによりフィボナッチ数列問題が改善され,時間的複雑度と空間的複雑度はいずれもO(n)であった.
  • fib(20)は、fib(19)とfib(18)を知るだけでよい.しかし、Tabulationを利用すると、すべてのフィボナッチの答えが保存されます.
  • リストの代わりに、最近の値のみを格納する2つの変数を使用します.
  • currentは最新の値で、前の値はpreferenceです.
  • 次のフィボナッチ値はcurrent(preved+current)であり、既存の値はprevedに格納される.
    • すべての値を保存する必要がない場合は、スペース最適化を行います.

    10.フィボナッチ数列空間の最適化


    質問する


    n番目のフィボナッチ数を計算するには,最近計算された2つの値を知る必要がある.fib最適化関数を空間複雑度O(1)で記述した.
    def fib_optimized(n):
    # 코드를 작성하세요. 

print(fib_optimized(1))    # 1을 출력
print(fib_optimized(2))    # 1을 출력
print(fib_optimized(3))    # 2을 출력
print(fib_optimized(4))    # 3을 출력
print(fib_optimized(5))    # 5을 출력

    に答える


    前述したダイナミックプログラム空間最適化を参照してください.

    コード#コード#

    def fib_optimized(n):
    # 코드를 작성하세요. 
    previous, current = 0, 1
    for i in range(1, n):
        previous, current = current, previous + current
    return current

# 테스트
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))
    # 콘솔 출력
987
53316291173
146178119651438213260386312206974243796773058

    11.甘酸っぱいビジネス分析


    率希は塾の休憩時間に友達と商売をしています.突然、手に持っている新しいもので稼ぐ最大の収益が気になりましたが...
    可能な最大収益を返す関数max_profitを作成してください.max_profitは、パラメータによって価格が設定されたリストprice_listを受け取り、販売する新しい「クリープ」の数countがリストされています.
    例えば、price_listが[100, 400, 800, 900, 1000]である場合.
  • 鳥1羽あたり100元
  • 新しいおもちゃ2個あたり400元
  • 3つの新しいおもちゃ800元
  • 4つの新しいおもちゃ900元
  • 5個の新しいおもちゃ1000元
    • 価格はこう決まっていますもし今日率希が新しいクリープを5つ売ったら、最大いくら稼ぐことができますか?
    もしあなたが1人の友达に3人売って、もう1人の友达に2人売ったら、800+400を稼ぐことができて、全部で1200元です.
    def max_profit(price_list, count):
    # 코드를 작성하세요.

# 테스트
print(max_profit([100, 400, 800, 900, 1000], 5))
    1200

    もんだいぶんせき

  • 最適なローカル構造は存在しますか?存在する.5つ売れた最大収益は次のように分けられます.

  • 一人に5個売る時の価格

  • 出来るだけ4個の最大収益+1個の出来るだけの最大収益を売る

  • 可能な限りの最大利益を3つ売る+2可能な限りの最大収益
    3つの状況はすべて知っていなければならない.一部の問題の答えを利用して既存の問題の答えを求めることができるので,この問題には最適な部分構造がある.
  • 冗長性の問題はありますか?存在する.

  • Dynamic Programmingはこの問題を解決できますか?—解決できる.
    • 最適な部分構造と重複する部分問題があるので、解決できます.

    12.甘酸っぱい長沙


    質問する


    率希は塾の休憩時間に友達と商売をしています.突然、手に持っている新しいもので稼ぐ最大の収益が気になりましたが...
    最大収益を返す関数max_profit_memoMemoizationを作成してください.max_profit_memoは、3つのパラメータを受信します.
  • price_list:価格リストがリストされています
  • count:販売する新しいおもちゃの数
  • cache:最大収益を格納する辞書
    • 例えば、price_listが[0, 100, 400, 800, 900, 1000]である場合.
  • 0個の新しいクリープ0元
  • 鳥1羽あたり100元
  • 新しいおもちゃ2個あたり400元
  • 3つの新しいおもちゃ800元
  • 4つの新しいおもちゃ900元
  • 5個の新しいおもちゃ1000元
    • 価格はこう決まっていますもし率希が新しいクリープを5つ売ったら最大いくら稼げるのでしょうか?
    もしあなたが1人の友达に3人売って、もう1人の友达に2人売ったら、800+400を稼ぐことができて、全部で1200元です.
    def max_profit_memo(price_list, count, cache):
    # 코드를 작성하세요.

    
def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

# 테스트
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))
    # 콘솔 출력
1200
2500
2400

    に答える


  • 基本的な状況を考えてみましょう.

  • memorizationなので、まずcacheにソリューションがあるかどうかをチェックします.

  • 再帰caseを考えてみましょう.重要なのは販売できる組み合わせを考えることです.
    """
가능한 조합
2개
2개, 0개
1개, 1개

3개
3개, 0개
2개, 1개

4개
4개, 0개
3개, 1개
2개, 2개

5개
5개, 0개
4개, 1개
3개, 2개
"""

    • コード#コード#

    def max_profit_memo(price_list, count, cache):
    # base case
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]
    
    # cache에 저장된 값이 있으면 반환
    if count in cache:
        return cache[count]
        
    # recursive case
    # price_list에 값이 존재하면 일단 profit에 저장
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0
        
    # 가능한 조합을 순회하며 profit을 갱신한다.
    for i in range(1, count//2+1):
        profit = max(profit,
            max_profit_memo(price_list, count-i, cache) + max_profit_memo(price_list, i, cache)
        )
    cache[count] = profit
    return cache[count]

    
def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

# 테스트
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))
    # 콘솔 출력
1200
2500
2400

    13.甘酸っぱい商売の陳述


    率希は塾の休憩時間に友達と商売をしています.突然、手に持っている新しいもので稼ぐ最大の収益が気になりましたが...
    Tabulationを使用して関数max_profitを作成してください.|可能な最大収益を返します.max_profitは、2つのパラメータを受信します.
  • price_list:価格リストがリストされています
  • count:販売する新しいおもちゃの数
    • 例えば、price_listが[0, 100, 400, 800, 900, 1000]である場合.
  • 0個の新しいクリープ0元
  • 鳥1羽あたり100元
  • 新しいおもちゃ2個あたり400元
  • 3つの新しいおもちゃ800元
  • 4つの新しいおもちゃ900元
  • 5個の新しいおもちゃ1000元
    • 価格はこう決まっていますもし率希が新しいクリープを5つ売ったら最大いくら稼げるのでしょうか?
    もしあなたが1人の友达に3人売って、もう1人の友达に2人売ったら、800+400を稼ぐことができて、全部で1200元です.
    def max_profit(price_list, count):
    # 코드를 작성하세요. 

# 테스트
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))
    # 콘솔 출력
2000
2400
1800

    に答える

    def max_profit(price_list, count):
    # 0개, 1개 가격 저장해두기
    table = price_list[:2] 
    
    # 2개 이상일 때 테이블에 기록
    for i in range(2, count+1):
        # price_list안에 있는 가격을 일단 profit에 저장
        if count < len(price_list):
            profit = price_list[i]
        else:
            profit = 0
            
        # i개를 팔수 있는 가능한 조합을 비교해서 더 큰 값을 profit에 저장
        for j in range(1, i//2+1): 
            profit = max(profit, table[j]+table[i-j])
        table.append(profit)
    return table[count]

# 테스트
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))
    # 콘솔 출력
2000
2400
1800
    [Node-Express]Middleware/next - Final Project
    [TIL]Python関数(parameters、default value、arguments)