UVa11566 - Let’s Yum Cha!(背包問題、動態規劃)

題目大意

一群好朋友要去吃港式飲茶，朋友們說好要一起出錢，同時不希望一樣的菜色出現兩次、或是一個人叫兩次以上的點心，看起來很膩，吃不到別的東西。
於是朋友們對每一樣菜列出了自己的喜愛程度，然後交由你來負責點菜，你需要滿足他們的平均最大喜愛程度
其中有 N 位朋友、每位朋友的預算為 x，有 K 個點心，入場費用是 T，並加收 10% 服務費(點心價+入場費)，就靠你幫忙算出拉

題目連結

重點觀念

• 能看得下那麼長的英文
• 使用 0,1 背包問題
• 花點巧思解決每盤不能點兩遍以上、一個人叫兩次以上的點心

分析

• 我們理所當然地了解到這是一個背包問題，選擇喜愛程度的點心並降低預算
• \(n+1\)，題目只有說到朋友有 n 個，但自己也會去吃所以是 \(n+1\)
• 注意 budget 計算
  • 不可以使用 \(nx * 0.1\) 作為服務費
    原因是因為服務費是根據我們的 x 再加一成，因此公式應該為 \(x + 0.1x\)，與 \(nx * 0.1\) 邏輯不符合。
  • 公式 \(x + 0.1x = 1.1x, x / 1.1 = 總預算\)
    我們的點心總費用必須再加上一層服務費，因此 \(1.1x\) 就是我們的總預算。
• 那我們要處理的背包問題如下
  • 我們必須將每位朋友的這種點心的喜愛程度加總，並算出價錢。
    使用迴圈解決
  • 每個菜色最多只能有兩盤
    我們可以讓每個種類的點心都複製一份，也就是說我們可以把每種點心放兩次到展示櫃中，這樣我們就解決 0,1 背包問題只能夠選擇拿或不拿。
  • 每個人最多只能點兩份
    我們可以假設背包最多只能放 \(2n\)，就可以解決 0,1 背包中的個數問題。
  • 如何找到平均最大喜愛程度
    我們透過 max(dp[0 ~ 2*N ][總預算]) 即可找出答案。
• 注意 Udebug 中第二個測資是錯誤的，請不要使用

參考連結

Uva11566 - Let’s Yum Cha! by txya900619
Uva11566 - Let’s Yum Cha! by pinghenotes

心得

首先我要先讚嘆各位能夠看完那麼長的英文，太佩服你們了，我自己看到一半就看不太下去了…。幾乎快要是看一點英文、做點別的事，這樣才好不容易把他看完…。

看來我的英文閱讀耐力是真的爛阿QQ。

在來就是太久沒有寫背包問題，很多演算法太久沒有用真的會忘記阿QQ，但其實都會有印象，只要看一下公式馬上就能夠想出來原理是甚麼，只是還需要看一下，感覺自己好沒用RRRR，沒辦法靠自己喚醒這個公式，需要答案幫忙QQQ。

總之希望我可以透過這個公式幫上自己未來的忙拉

還有就是希望好心人可以幫我解決為甚麼使用我的方式計算 budget，會是 WA QQ。真的很需要拜託了！

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
//#define int long long
#define MAXN 100020
using namespace std;
int n, x, t, k;
int dp[12*2][12*100];
//點心的展示櫃
vector<pair<int,int>> item; //price value 

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> x >> t >> k && n){
        memset(dp, 0, sizeof(dp));
        item.clear();

        n++; //include me 自己也會去吃

        //UVa AC 作法，解決小數點精度問題。
        //其中需要 (float) 1.1 是因為在 double 時小數點較多，容易導致精度不準確，
        //1.1 我們只需要最多一個小數點即可，避免精度不精因此使用 float
        //budget = 總預算 / (服務費 + 總花費) - 茶費
        int budget = (n * x) / (float) 1.1 - (n * t);

        for(int i = 0; i < k; i++){ //計算每一個點心價格與所有朋友的喜愛程度總和
            int value=0, sum=0, price;
            cin >> price;
            for(int j = 0; j < n; j++){
                cin >> value;
                sum += value;
            }
            //展示櫃直接放兩個，解決 0,1 背包問題
            item.push_back(make_pair(price, sum));
            item.push_back(make_pair(price, sum)); // 2(n+1)
        }

        for(int i = 0; i < item.size(); i++){ //展示櫃裡的東西選擇拿或不拿
            int price = item[i].first;
            int value = item[i].second;
            for(int j = n*2; j > 0; j--){ //最多只能點 n*2點心
                for(int k = budget; k >= price; k--){ //dp 0,1 背包問題
                    //判斷增加這個點心，會不會帶來更大的朋友喜愛程度
                    dp[j][k] = max(dp[j][k], dp[j-1][k-price] + value);
                    //不增加會不會比較好 
                    dp[j][k] = max(dp[j][k], dp[j-1][k]);
                }
            }
        }

        int ans = 0;
        //找出最好的答案
        for(int i = 0; i <= n*2; i++) ans = max(ans, dp[i][budget]);
        cout << setprecision(2) << fixed << (double) ans / n << '\n';
    }
    return 0;
}