-
算法实验周
算法实验周
********************************
题目相关知识说明
—
所做任务说明及
< br>文档编号：
NUC-2013-
A07
< br>-01
版
本：
1.0
作
者：
张家杰
崔风川
打印日期：
2013.12.27
拷贝份数：
1
?
2
0
1
3
中
北
大
学
计
算
机
与
控
< br>制
工
程
学
院
算法实验周
1
、所做任务：商店购物问题
某商店中每种商品都有一个价格。例如，一朵花的价格是
2
ICU(ICU
是信
息学竞赛的货币的单位）；一个花瓶的价
格是
5
ICU
。为了吸引更多的顾客
，商
店提供了特殊优惠价。
特殊优惠商品是把一种或几种商品分
成一组。
并降价销售。
例如
:3
朵花的价格不是
6
而是
5
ICU
；
2
< br>个花瓶加
1
朵花是
10
ICU
不是
12
ICU
。
编一个程序，计算某个顾客所购商品应付的费用。
要充分利用优惠价以使
顾客付款最小。
其中，
顾客所购商品信息从
文件中读取，
优惠信息从
文件中读取，
最后将结果输出到
文件中。
2
、相关知识说明
蛮力法：
是一种简单直接的解决问题
的办法，
常常直接基于问题的描述和所涉及的概
念的定义。
蛮力法所依赖地基本技术：扫描技术
蛮力法的关键：依次处理所有元素
蛮力法的优点：
（
< br>1
）理论上可以解决计算领域的所有问题
（
2
）经常用来解决一些小规模的问题
（
3
）可以作为某类问题
时间性能的底限，来衡量同样问题的更高效算
法。
动态规划：是一种使多阶段决策过程最优的通用方法。
如果问题是由交叠的子问题所构成的，我们就可以用动态规划技术解决它。
一般来说，
这样的子问题出现在对给定问题求解的递推关系中，
这个递推关系中
包含了相同类型的更小子问题的解。
动态规
划法建议，
与其对交叠的子问题一次
又一次的求解，
还不如对每个较小的子问题只求解一次并把结果记录在表中，
这
样就可以在表中得出原始问题的解。
算法实验周
********************************
数据结构设计说明
—
文档编号：
NUC-2013-
A07
-02
版
本：
1.0
作
者：
张家杰
崔风川
打印日期：
2013.12.27
拷贝份数：
1
?
2
0
1
3
中
北
大
学
计
算
机
与
< br>控
制
工
程
学
院
算法实验周
1
、
为所购商品信息建立一个类
GoodsInfo
，
该类包含
id
（商品编
号）
、
count
（商
品数量）
、
price
（商品
单价）三个属性。
2
、对于每种优惠
，建立一个类
DiscountInfo
，该类包含
cateOfGoods
（该优惠
中商品的种类）
、
value
（该优惠的价值）
、
goods
（该优惠中的商品信息）三个属
性，其中
goods
是
HasnMap
类型。
3<
/p>
、
为了从
文件中
读取数据，
新建
InputFile
类
，
该类包含
cateOfGoods
（
购物筐中商品的种类）
、
map_Goods
< br>（购物筐中商品的信息）两个属性，其中
map_Goods
是
HashMap
类型。
4
、为了从
文件中读
取优惠的信息，新建
OfferFile
类，该类包含
cateOfDiscount
（优惠的种类）
、
map_Discount
（优惠的信息）两个属性，其中<
/p>
map_Discount
是
HashM
ap
类型。
5
、新建一个
OutputFile
类，其构造方法可向
文件中输出数据。
算法实验周
********************************
—
程序模块及流程设计
文档编号：
NUC-2013-
A07
-03
版
本：
1.0
作
者：
张家杰
崔风川
打印日期：
2013.12.27
拷贝份数：
1
算法实验周
（
1
）程序模块
< br>?
2
0
1
3
中
北
大
学
计
算
机
与
控
制
工
程
学
院
数据结构定义模块：
定义了购物筐中的商品信息和优惠方案中的优惠信息。
文件读取和输出模块：
从文件中读取所购商品信息和有关的优惠信息，程序运行结束后将结果
输出
到
文件中。
算法核心模块：
两种算法——蛮力法
和动态规划方法共用上面的数据结构定义模块与文
件读取和输出模块，运行程序并将结果
输出
。
（
2
）流程设计
蛮力法：
从文件中读取商品
信息和优惠信息
循环测试
n
中优惠方案
是否可行
不可用
最少花费为商品数量
与原价乘积的和并保
存到数组的相应位置
用选择排序计算数组
中的最小值并输出
可用
商品数量减去优惠方案
中对应的商品数，最小
花费加上该优惠的价值