【範例】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]
}