【筆記】DP:Top-down vs. Bottom-up

【範例】UVA 11450 Wedding shopping【題解
【題意】在不超出預算 (M),且每一類服裝購買一件的條件下,最大化總消費金額。(服裝種類有C種。)
【參考書】Chapter 3.5 of “Competitive Programming 3”

目錄

Top-down

  • 利用遞迴(recursion)方式實作,比較直觀。
  • 因為只計算需要的部分,速度通常比較快。但如果需要計算多數的狀態,則進出函式多次的結果,可能導致時間更長。
  • 通常使用的記憶體容量較多,不像Bottom-up的方式可以進行記憶體空間的優化。
  • 【解題想法】
    • dp[money][g]:預算 money,從第 g 種服裝開始購買的最大花費。
    • 函式 ship(money, g):計算dp[money][g]
    • 答案 ans = shop(M, 0),top-down 計算的結果。
//題目要求最大值,狀態初始值全設為-1
memset(dp, -1, sizeof(dp));
//UVA 11450 Wedding shopping (Top-down)
int shop(int money, int g){
    //當預算小於0時無解,回傳-INF
    if (money < 0) return -1e9;
    //服裝種類 0 ~ C-1,當計算到第C種時,遞迴終止。
    //回傳總花費 = 總預算 - 剩餘金額
    if (g == C) return M - money;
    int &ans = dp[money][g]; //使用參照,節省記憶體
    if (ans != -1) return ans; //記憶化,避免重複的計算
    //枚舉第g種類的每一件衣服
    //price[g][0]:第g種類的衣服件數
    //price[g][i]:第g種類的第i件衣服的價格
    for (int i = 1; i <= price[g][0]; i++){
        ans = max(ans, shop(money - price[g][i], g+1));
    }
    return ans;
}

Bottom-up

  • 利用迴圈(iteration)方式填表,計算所有可能的狀態。
  • 有時可以優化節省記憶體。
  • 【解題想法】
    • bool dp[2][M]:紀錄一個“剩餘”金額是否在購買的過程出現過
    • dp[pre][M]:上一次購買的狀態
    • dp[cur][M]:目前購買的狀態
    • 答案:M – “dp[pre] 的最小值”
bool dp[2][M]; //check whether a state is reachable
memset(dp, false, sizeof(dp));

//先從第0種服裝類別開始考慮
for (int i = 1; i <= price[0][0]; i++){
    if (M - price[0][i] >= 0){
        dp[0][M - price[0][i]] = true;
    }
}
//UVA 11450 Wedding shopping (Bottom-up)
int cur = 1, pre = 0;
//循序計算第 1 ~ C-1 種服裝類別
for (int g = 1; g < C; g++){
    //初始化
    for (int money = 0; money < M; money++){
        dp[cur][money] = false;
    }
    for (int money = 0; money < M; money++){
        //如果金額money曾在上一次購買中出現
        if (dp[pre][money]){
            for (int i = 1; i <= price[g][0]; i++){
                //如果金額money足夠購買第g種類的第i件衣服
                if (money - price[g][i] >= 0){
                    dp[cur][money - price[g][i]] = true;
                }
            }
        }
    }
    swap(pre, cur); //對調dp[pre][money]與dp[cur][money]
}
分享本文 Share with friends