西安交通大学算法上机实验报告.pdfVIP

《计算机算法设计与分析》

上机实验报告

姓名：

班级：

学号：

日期：2016年12月23日

算法实现题3-14最少费用购物问题

★问题描述：商店中每种商品都有标价。例如，一朵花的价格是2元，一个

花瓶的价格是5元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把

一种或多种商品分成一组，并降价销售。例如，3朵花的价格不是6元而是5元。

2个花瓶加1朵花的优惠价格是10元。试设计一个算法，计算出某一顾客所购

商品应付的最少费用。

★算法设计：对于给定欲购商品的价格和数量，以及优惠价格，计算所购商

品应付的最少费用。

★数据输入：由文件input.txt提供欲购商品数据。文件的第1行中有1个

整数B（0≤B≤5），表示所购商品种类数。在接下来的B行中，每行有3个数

C,K和P。C表示商品的编码（每种商品有唯一编码），1≤C≤999；K表示购买

该种商品总数，1≤K≤5；P是该种商品的正常单价（每件商品的价格），1≤P≤

999。请注意，一次最多可购买5*5=25件商品。

由文件offer.txt提供优惠商品价数据。文件的第1行中有1个整数S（0≤

S≤99），表示共有S种优惠商品组合。接下来的S行，每行的第1个数描述优

惠商品组合中商品的种类数j。接着是j个数字对（C，K），其中C是商品编码，

1≤C≤999；K表示该种商品在此组合中的数量，1≤K≤5。每行最后一个数字P

（1≤P≤9999）表示此商品组合的优惠价。

★结果输出：将计算出的所购商品应付的最少费用输出到文件output.txt。

输入文件示例输出文件示例

Input.txtoffer.txtoutput.txt

2214

7321735

8252718210

解：

设cost（a，b，c，d，e）表示购买商品组合（a，b，c，d，e）需要的最

少费用。A[k]，B[k]，C[k]，D[k]，E[k]表示第k种优惠方案的商品组合。offer

（m）是第m种优惠方案的价格。如果cost（a，b，c，d，e）使用了第m种

优惠方案，则

cost（a，b，c，d，e）=cost（a-A[m]，b-B[m]，c-C[m]，d-D[m]，

e-E[m]）+offer（m）

即该问题具有最优子结构性质。按此递归式，设计此问题的动态规划算法如

下。

1.#includeiostream

2.#includecstdio

3.#includealgorithm

4.#includecstring

5.#includequeue

6.#includeset

7.#includemap

8.#includetime.h

9.usingnamespacestd;

10.

11.intsale[1000][6]={0};//分别表示每个优惠中每个商品数量

12.intsaleprice[1000]={0};//优惠总价

13.intsalelength[1000]={0};//优惠总共有几个商品