UVa 233 Package Pricing

题目分析题目描述了一家销售444种尺寸节能灯泡的公司这些灯泡尺寸分别用字符a、b、c、d表示。公司提供若干优惠套餐每个套餐有目录编号、价格和包含的灯泡组合。顾客需要购买特定数量的灯泡要求找出最便宜的套餐组合方式使得购买的灯泡数量满足或超过顾客需求并输出总价和套餐清单。解题思路状态表示本题需要使用状态压缩动态规划DP\texttt{DP}DP将444种尺寸的需求量编码为一个状态。每种尺寸的需求量最多是多少题目没有明确给出但根据状态数组memo[1048576]可以推断每种尺寸的最大需求量为202020因为(201)4194481(201)^4 194481(201)4194481远小于104857610485761048576实际测试发现最大需求量为202020。使用base数组计算状态索引indexcount[0]×base[0]count[1]×base[1]count[2]×base[2]count[3]×base[3] index count[0] \times base[0] count[1] \times base[1] count[2] \times base[2] count[3] \times base[3]indexcount[0]×base[0]count[1]×base[1]count[2]×base[2]count[3]×base[3]其中base[0](need[1]1)×(need[2]1)×(need[3]1)base[1](need[2]1)×(need[3]1)base[2]need[3]1base[3]1 \begin{aligned} base[0] ( need[1] 1 ) \times ( need[2] 1 ) \times ( need[3] 1 ) \\ base[1] ( need[2] 1 ) \times ( need[3] 1 ) \\ base[2] need[3] 1 \\ base[3] 1 \end{aligned}base[0]base[1]base[2]base[3]​(need[1]1)×(need[2]1)×(need[3]1)(need[2]1)×(need[3]1)need[3]11​动态规划转移定义memo[state]存储三个信息price达到该状态的最小花费index达到该状态时最后选择的套餐编号parent达到该状态的前一个状态。初始状态memo[0] {0, -1, -1}其他状态初始化为极大值1E20。对于每个状态state解码出当前已购买的灯泡数量current[4]。然后尝试添加每种套餐packages[i]得到新状态nextnext[j]min⁡(current[j]packages[i].supply[j], need[j]) next[j] \min(current[j] packages[i].supply[j],\ need[j])next[j]min(current[j]packages[i].supply[j],need[j])如果新状态的price大于当前状态花费加上套餐价格则更新memo[next]。结果回溯求出maxState getIndex(need)后memo[maxState].price即为最小总价。然后从maxState开始回溯记录每个状态使用的套餐通过counter累加套餐的使用次数。最后输出结果时套餐按目录编号升序输出使用次数超过111时用括号注明。注意事项由于顾客请求中可能包含重复尺寸需要在输入时累加统计。输出的价格保留两位小数使用fixed和setprecision(2)。每个测试用例的counter在使用前需要清空。代码实现// Package Pricing// UVa ID: 233// Verdict: Accepted// Submission Date: 2016-06-21// UVa Run Time: 0.460s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 套餐结构体structpackage{intcatalogue;// 套餐编号doubleprice;// 套餐价格intsupply[4];// 四种尺寸灯泡的个数};// DP状态结构体structchoice{doubleprice;// 达到该状态的最小花费intindex,parent;// 最后选择的套餐编号和前一个状态};intn;// 套餐数量vectorpackagepackages;// 存储所有套餐intbase[4];// 用于状态编码的基数doubleminPrice;// 最小总价mapint,intcounter;// 统计每个套餐的使用次数choice memo[1048576];// DP状态数组// 根据当前数量数组计算状态编码intgetIndex(intcount[]){intindex0;for(intj0;j4;j)indexcount[j]*base[j];returnindex;}// 动态规划求解最便宜套餐组合voiddp(package need){// 计算基数数组base[0](need.supply[1]1)*(need.supply[2]1)*(need.supply[3]1);base[1](need.supply[2]1)*(need.supply[3]1);base[2]need.supply[3]1;base[3]1;intcurrent[4],next[4],maxStategetIndex(need.supply);// 初始化DP状态为极大值for(inti0;imaxState;i)memo[i](choice){1E20,-1,-1};// 初始状态花费为0memo[0](choice){0,-1,-1};// 遍历所有状态for(intstate0;statemaxState;state){intsstate;// 解码当前状态得到已购买的灯泡数量for(inti0;i4;i)current[i]s/base[i],s%base[i];// 尝试每种套餐for(inti0;in;i){// 计算添加套餐i后的新状态for(intj0;j4;j)next[j]min(current[j]packages[i].supply[j],need.supply[j]);intindexgetIndex(next);// 如果新状态的花费可以更小则更新if(memo[index].pricememo[state].pricepackages[i].price)memo[index](choice){memo[state].pricepackages[i].price,i,state};}}// 回溯统计套餐使用次数counter.clear();for(intstatemaxState;state0;statememo[state].parent)counter[packages[memo[state].index].catalogue];// 记录最小总价minPricememo[maxState].price;}intmain(){ios::sync_with_stdio(false);string line;while(getline(cin,line)){packages.clear();// 读取套餐数量nstoi(line);// 读取n个套餐信息for(inti1;in;i){getline(cin,line);istringstreamiss(line);package p;issp.cataloguep.price;// 初始化四种尺寸的数量为0memset(p.supply,0,sizeof(p.supply));charsize;intcount;while(isssizecount)p.supply[size-a]count;packages.push_back(p);}// 读取顾客请求数量getline(cin,line);intmstoi(line);// 处理每个顾客请求for(inti1;im;i){getline(cin,line);istringstreamiss(line);package need;memset(need.supply,0,sizeof(need.supply));charsize;intcount;while(isssizecount)need.supply[size-a]count;dp(need);// 输出结果请求编号、冒号、总价右对齐宽度8couti:setw(8)right;coutfixedsetprecision(2)minPrice;// 输出套餐组合按编号升序for(autoc:counter){if(c.second0)cout c.first;if(c.second1)cout(c.second);}coutendl;}coutendl;}return0;}