# 【題解】UVA 11450 Wedding shopping

【題目敘述】https://vjudge.net/problem/UVA-11450
【解題想法】DP

#### Top-down DP

#include <iostream>
#include <cstring>
using namespace std;
int T, M, C;
int dp[205][25];
int price[25][25];

int shop(int money, int g){
if (money < 0) return -1e9;
if (g == C) return M - money;
int &ans = dp[money][g];
if (ans != -1) return ans;
for (int i = 1; i <= price[g][0]; i++){
ans = max(ans, shop(money - price[g][i], g+1));
}
return ans;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--){
cin >> M >> C;
for (int i = 0; i < C; i++){
cin >> price[i][0]; // K
for (int j = 1; j <= price[i][0]; j++){
cin >> price[i][j];
}
}
memset(dp, -1, sizeof(dp));
int ans = shop(M, 0);
if (ans < 0) cout << "no solution\n";
else cout << ans << "\n";
}
return 0;
}

#### Bottom-up DP

#include <iostream>
#include <cstring>
using namespace std;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T, M, C;
cin >> T;
while (T--){
cin >> M >> C;
int price[25][25] = {0};
for (int i = 0; i < C; i++){
cin >> price[i][0];
for (int j = 1; j <= price[i][0]; j++){
cin >> price[i][j];
}
}
bool dp[2][M]; //check whether a state is reachable
memset(dp, false, sizeof(dp));
for (int i = 1; i <= price[0][0]; i++){
if (M - price[0][i] >= 0){
dp[0][M - price[0][i]] = true;
}
}
int cur = 1, pre = 0;
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++){
if (dp[pre][money]){
for (int i = 1; i <= price[g][0]; i++){
if (money - price[g][i] >= 0){
dp[cur][money - price[g][i]] = true;
}
}
}
}
swap(pre, cur);
}
int ans = -1;
for (int i = 0; i < M; i++){
if (dp[pre][i]){
ans = i;
break;
}
}
if (ans >= 0) cout << M - ans << "\n";
else cout << "no solution\n";
}
return 0;
}