2013-07-07 21:23:07Morris
[UVA][dp] 10898 - Combo Deal
D: Combo Deal
A fast food store offers a series of ``combo meal deals" in addition to
individually priced items. For example, the menu at the store may look
like this:
| D: Combo Deal |
Hamburger $3.49Buying a combo is cheaper than buying its items individually.
Fries $0.99
Pop $1.09
Ice Cream $2.19
Value Meal (1 Hamburger, 1 Fries, 1 Pop) $4.79
Lovers-Only (2 Hamburgers, 2 Fries, 2 Pops, 1 Ice Cream) $9.99
A parent of many kids (or a coach of many students) face this recurring
problem: I need to get, say, 9 hamburgers, 6 fries, and 8 pops. How do I
fit this into the menu, using the combo deals optimally, so as to pay
as little as possible? Note that I am a conservativist, so I don't buy
more food than I need.
Input
The input contains several test cases, each of them with a menu and several orders.
- Menu: Individual items, then combos.
- (a)
- Individual items: number of items
, then their prices (at most $10 each).
- (b)
- Combos: number of combos (at most 8), then for each combo, its composition as an
-tuple of quantities and its price.
Example: the sample input below encodes the menu above.
- Orders: number of orders (at most 10), then for each order, an -tuple of the wanted quantities. Each element in the tuples is at most 9.
All prices are integers in cents.
Output
For each order of each case, output the minimum payment in cents on its own line.
Sample Input
4 349 99 109 219 2 1 1 1 0 479 2 2 2 1 999 2 9 6 8 0 9 6 8 5
Sample Output
4139 4700
套餐組合一定是便宜的，因此使用動態規劃找最佳解。
但因為不會多買跟少買，又因為有最多六個，每個數量不超過 <= 9。
因此可以壓縮成十進制數 <= 999999。
原本想說進行陣列標記，但有點麻煩就使用了 map<int, int> 當作陣列。
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int A[10];
int B[10][10], cB[10];
int I, C;
map<int, int> dp;
int dfs(int state) {
if(state == 0) return 0;
if(dp.find(state) != dp.end())
return dp[state];
int &val = dp[state];
val = 0xfffffff;
int v[6] = {}, i, j, xx;
for(i = I-1; i >= 0; i--)
v[i] = state%10, state /= 10;
for(i = 0; i < C; i++) {
for(j = 0; j < I; j++)
if(v[j] < B[i][j])
break;
if(j != I) continue;
xx = 0;
for(j = 0; j < I; j++) {
v[j] -= B[i][j];
xx = xx*10 + v[j];
}
val = min(val, dfs(xx)+cB[i]);
for(j = 0; j < I; j++)
v[j] += B[i][j];
}
for(i = 0; i < I; i++) {
if(v[i] == 0) continue;
v[i]--;
xx = 0;
for(j = 0; j < I; j++)
xx = xx*10 + v[j];
val = min(val, dfs(xx)+A[i]);
v[i]++;
}
return val;
}
int main() {
int i, j;
while(scanf("%d", &I) == 1) {
for(i = 0; i < I; i++)
scanf("%d", &A[i]);
scanf("%d", &C);
for(i = 0; i < C; i++) {
for(j = 0; j < I; j++)
scanf("%d", &B[i][j]);
scanf("%d", &cB[i]);
}
int q, x;
scanf("%d", &q);
dp.clear();
while(q--) {
int xx = 0;
for(i = 0; i < I; i++) {
scanf("%d", &x);
xx = xx*10 + x;
}
printf("%d\n", dfs(xx));
}
}
return 0;
}