网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
购物问题
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 18:45 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 18:45 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 18:45 |
输入文件 | shopping.in | 输出文件 | shopping.out |
【问题描述】购物问题(shopping.cpp/c/pas)Zju1524
建造太空梯需要的物品非常多,墨老师每周都会交给楚继光一张购物清单,他需要购买清单上所列的物品并且必须全部买齐。最开始,楚继光总是穿梭于商店的过道之间,对每样商品选择最便宜的价格购买,但是他逐渐地厌倦了这种方式,并开始了一种新的尝试──对于商店中的每条过道只走一遍,并严格按照清单上物品的顺序购物。现在你要写一个程序来帮助他购物。你所拥有的信息除了清单所列的物品之外,还包括在他选择的整条路线上依次出现的商品和它的价格,你的任务是计算他购齐所有货物的最小花费。
举个例子,如图所示,楚继光需要购买的货物标号依次是1,1,2,20,他必须从下表中依次选择这四样物品,并使总花费最小(在某些情况下,他也可能根本无法找到一种方案购全所有商品),在这个例子中,他的最小花费是21.30元,即选择0.30元和1元的1号商品,然后选择10元的2号和20号商品。
【输入格式】
第一行两个数,分别表示清单物品数n (n ≤100),路线上物品数m(m ≤1000), 接下来一行n个整数描述购物清单的物品,接下来m行每行一个整数和实数,表示物品的编号和价钱。
【输出格式】
如果可以买到所有物品,打印最少花费,精确到小数点后两位。
如果不行,打印“Impossible”
【样例输入1】
4 8
1 1 2 20
2 0.29
1 0.30
20 0.15
1 1.00
5 0.05
2 10.00
20 20.00
20 10.00
【样例输出1】
21.30
【样例输入2】
2 3
1 2
2 0.05
1 10.00
1 3.00
【样例输出2】
Impossible