演算法

通常實作題的3、4題都會運用到資料結構或者是演算法，而且通常不會只是運用到單一的資料結構或演算法，所以，看到題目的時候，可以先盤點一下學過的方法，看有沒有適合的解決方法。

重要演算法

這裡介紹貪婪法則、分治法及動態規劃，簡單的說，貪婪法則就是先看局部(眼前)的解答，從局部解答開始一步一步找，會找到整體最佳解。分治法跟貪婪法則有點像，也是將問題分解成小問題，只是，局部最佳解的組合不一定是整體最佳解，從合併過程中去尋找整體最佳解。動態規劃是基於分治法，只是透過記憶過去算過的答案，節省重複計算的時間。

• 貪婪法則 (greedy method)
  • 【筆記】Greedy 貪心法則
  • 貪婪(Greedy)演算法 (黃建庭老師)
    • 會稱為貪婪法則，就是因為只注意局部(眼前)的最佳解，可能看不到整體最佳解，所以，只適用於，局部(眼前)最佳解的組合會是整體最佳解的問題
    • 前提
      • 之前所選擇的解答不會影響後面所選擇的解答
      • 不斷的選擇局部的最佳解，全部選取結束後就獲得整體的最佳解
    • Step1)定義貪婪準則
      • 根據此貪婪準則，不斷找出目前小問題的最佳解。
    • Step2)不斷重複貪婪準則，直到解決問題為止
      • 不斷的使用貪婪準則,，找出每個小問題的最佳解，直到解決問題為止。
    • 當我們要將所有撲克牌排順序時，要怎麼排?
      • 從尋找最小值(梅花1)開始嗎?
        • 以撲克牌為例，我們知道梅花1最小，所以，只要注意是不是梅花1。但是，通常數字排序時不知道最小值，所以，要一一比較才能找出最小值。找到之後，再從其他的去找下一個最小值，這是selection sort的原理。
  • Greedy Algorithm
    • Greedy Choice Property
    • Optimal Substructure
  • c575 基地台 (基礎演算法1)
    • APCS 2017年3月第4題
    • 要找到基地台最小直徑，如果透過窮舉法列出基地台可能位置的所有組合，會很複雜
      • 先分解(簡化)問題，反過來想，是否可以從最小直徑(也就是1)，能涵蓋多少點，用這樣去計算所需要的基地台
        • 逐步增加直徑，一直到正好是所給定的基地台數量，就能找到最小直徑
      • 當最小直徑與最大可能直徑差異很大的時候，直徑從1開始逐步增加直徑，就會很慢，所以，借用二元搜尋的概念來降低尋找的次數
  • c471 物品堆疊 (Stacking) (基礎演算法1)
    • APCS 2017年10月第4題
    • 要找到堆疊整體最佳解，如果透過窮舉法列出所有組合，再去求最低成本，會花太多時間
      • 先**分解(簡化)問題，**透過相鄰兩者的移動成本比較，進行排序，排序後，就能找到整體最佳解答
• 分治法 (Divide-and-Conquer)
  • 當我們要將所有撲克牌排順序時，要怎麼排?
    • 從尋找最小值(梅花1)開始嗎?
      • 這是selection sort的原理，也是貪婪法則的基本原理，但是，用在排序時，會花很多時間去排序，並不適合。
    • 如果分成兩張一堆，每一堆先排序，兩兩相比很容易，接下來，因為每一堆都已經排序，合併時速度就很快
      • 這就是merge sort的原理，這就是分治法的基本原理
  • 主要步驟
    • 切割
      • 將問題切割成若干個子問題，通常是均勻地切成兩個。
    • 分別對子問題遞迴求解。
      • 遞迴就會繼續切割
    • 合併
      • 將子問題的解合併成原問題的解。
  • 反序數量
    • APCS 2018年6月第4題
  • f315 低地距離 (本週的實作題)
    • 2020年10月第4題
• 動態規劃 (dynamic programming)
  • 演算法筆記系列 — Dynamic programming 動態規劃
  • Dynamic Programming (Fibonacci)
  • Dynamic Programming (Making Change)
  • Dynamic Programming (Longest Common Subsequence)
  • Dynamic Programming
    • 階乘
    • Dynamic Programming: recurrence
      • Dynamic Programming = Divide-and-Conquer Method + Memoization
    • Dynamic Programming: counting / optimization
  • 動態規劃(Dynamic Programming) (黃建庭老師)
    • 動態規劃的解題步驟
      • 定義大問題與小問題的關係
        • 分治(Divide-and-Conquer): 將問題分為大小問題，先解決小問題)
      • 使用陣列儲存小問題的解
        • Memoization/以空間換取時間
      • 是否需要找出最佳解路徑? 若需要最佳解的路徑，使用陣列紀錄解的過程，再印出最佳解的路徑
  • e465 置物櫃分配 (DP)
    • 2018年10月第4題
  • g278 美食博覽會 (DP)
    • 2021年9月第4題
  • f314 勇者修煉 (DP)
    • 2020年10月第3題

觀念題

• 105年10月 觀念題
  • 第1題
  • 第5題
  • 第10題
  • 第11題

實作題

• e465 置物櫃分配 (DP)

  • 2018年10月第4題

• g278 美食博覽會 (DP)

  • 2021年9月第4題

• f312 人力分配

  • 2020年10月第1題
  • ** 小心測資裡會有最大收益是負數的情況

• f314 勇者修煉 (DP)

  • 2020年10月第3題

  1 5 2 1 4 -7 4

  • 如果只有一層，我們先分析一下，能不能由最大值開始，每次只走沒走過的路，如果有選項，就找周邊下個最大值 (貪婪演算法)?
    • 如果第一步是[0,2]
      • [0,2] → [0,1] → [0,0] = 7
        • 前面比後面大
    • 如果第一步是[0,4]
      • [0,4] → [0,3] → [0,2] → [0,1] → [0,0] = 4
  • 我們仔細找一下最大值
    • 如果第一步是[0,0] (以0開始)
      • [0,0]→[0.1]→[0,2]=7 (停在這裡得到最大)
      • [0,0]→[0.1]→[0,2]→[0,3]→[0,4]=4
    • 如果第一步是[0,1]
      • [0,1]→[0,0]=3
      • [0,1]→[0,2]=5 (停在這裡得到最大)
      • [0,1]→[0,2]→[0,3]→[0,4]=4
    • 如果第一步是[0,2]
      • [0,2]→[0,3]→[0,4]=1
      • [0,2]→[0.1]→[0,0]=7
    • 如果第一步是[0,3]
      • [0,3]→[0,4] = -3
      • [0,3]→[0,2]→[0,1]→[0,0]=0
    • 如果第一步是[0,4]
      • [0,4]=4 (停在這裡得到最大)
      • [0,4]→[0,3]→[0,2]→[0,1]→[0,0]=4
  • 似乎可以用貪婪演算法，但是，如果資料是這樣的話:

  1 6 2 1 3 -1 4 1

  • 可看到從前幾步的的最大解，不保證找到整體最大解
    • 第一步選擇是[0,4]
    • 但是，最大值是10，所以，不能用貪婪演算法，也就是從前幾步的的最大解，不保證找到整體最大解

• 從以上找到最大值的過程中，可以看到找的過程中會重複很多的計算，如果儲存這些計算結果，應該可以節省運算時間 (運用到動態規劃的概念)

• f315 低地距離 (分治)