# 題目: UVa 11566 - Let's Yum Cha

# 題目說明

中文題目說明

---

INPUT:
第一行輸入4個整數N、x、T、K
你與N位朋友去飲茶，每人最多付x元，需要支付T元的茶費，總共有K種點心可以點
接下來有K行，每行有N + 2個整數，第一個為點心的價格，後面N + 1個為每人的滿意度
當N、x、T、K為0時結束程式

---

OUTPUT:
輸出最大的mean favour value

# 解題方法

先計算預算P
P = (總人數 * 每人最多支付金額) / 服務費 - (每個人的茶費)
寫成數學算式如下:
P = (++N * x) / (float)1.1 - (N * T);

---

接下來輸入資料存到vector< pair<int, int> > pf
前者為點心的價格，後者為所有人滿意度之合
每樣點心最多點兩個，所以存兩次

---

之後同樣用knapsack problems的概念跑動態規劃
定義一個dp[i][j]
代表選了i個點心，總價格為j元

轉移方程為:
dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - price] + favour)

---

最後將價格固定，遍歷所有選擇數量的最大滿意度

# 參考程式碼

#include <iostream>
#include <vector>
#include <memory.h>
#include <iomanip>

using namespace std;

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, x, T, K;
	int P;
	int dp[23][1001];

	while (cin >> N >> x >> T >> K, N + x + T + K)
	{
		// calculate the tatal (maximum) price
		P = (++N * x) / (float)1.1 - (N * T);
		//cout << P << "\n";

		vector< pair<int, int> > pf;
		memset(dp, 0, sizeof(dp));
		int ans = 0;

		// store price and favour index
		// put each of the dim sums twice in the vector
		for (int i = 0; i < K; ++i)
		{
			int a, b = 0, tmp;

			cin >> a;
			for (int j = 0; j < N; ++j) cin >> tmp, b += tmp;

			pf.push_back({ a, b });
			pf.push_back({ a, b });
		}

		for (int k = 0; k < pf.size(); ++k)
		{
			auto& [price, favour] = pf[k];
			for (int i = N * 2; i > 0; --i) for (int j = P; j >= price; --j)
				dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i - 1][j - price] + favour));
		}

		for (int i = 0; i <= N * 2; ++i) ans = max(ans, dp[i][P]);
		cout << setprecision(2) << fixed << (double)ans / N << "\n";
	}

	return 0;
}

# 參考資料

https://summon528.github.io/2017/12/07/UVA-11566-Let-s-Yum-Cha/
https://blog.csdn.net/samlee946/article/details/38481533
http://unfortunatedog.blogspot.com/2013/07/11566-lets-yum-cha_23.html