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

《西安交通大学算法上机实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机算法设计与分析》上机实验报告姓名：班级：学号：日期：2016年12月23日算法实现题3-14最少费用购物问题★问题描述：商店中每种商品都有标价。例如，一朵花的价格是2元，一个花瓶的价格是5元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销售。例如，3朵花的价格不是6元而是5元。2个花瓶加1朵花的优惠价格是10元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。★算法设计：对于给定欲购商品的价格和数量，以及优惠价格，计算所购商品应付的最少费用。★数据输入：由文件input.txt提供欲购商品数据。文件的第1行中有1个整

2、数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

3、（1≤P≤9999）表示此商品组合的优惠价。★结果输出：将计算出的所购商品应付的最少费用输出到文件output.txt。输入文件示例输出文件示例Input.txtoffer.txtoutput.txt221473217358252718210解：设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

4、]，c-C[m]，d-D[m]，e-E[m]）+offer（m）即该问题具有最优子结构性质。按此递归式，设计此问题的动态规划算法如下。1.#include   2.#include   3.#include   4.#include   5.#include   6.#include   7.#include 

5、0};    //分别表示每个优惠中每个商品数量   12.int saleprice[1000] = {0};  //优惠总价   13.int salelength[1000] = {0}; //优惠总共有几个商品   14.int salenumber[1000][1000] = {0};   //优惠商品的ID   15.int good[6][4] = {0};       //1 -> number   2 -> price  3 -> last num  16.int num[1000];              //商品ID   17.int dp[

6、6][6][6][6][6];    18.int n,m;  19.  20.void input()  21.{  cout<<"input.txt"<>n;  23.        for(int i = 1; i  <= n; i++)  24.        {  25.            cin>>good[i][1]>>good[i][3]>>good[i][2];  26.            num[i] = good[i][1];  27.        }  28.cout<<"offer.txt"

7、<>m;  30.        for(int i = 1; i <= m; i++)  31.        {  32.                cin>>salelength[i];  1.                for(int j = 1; j <= salelength[i]; j++)  2.                {  3.                        cin>>salenumber[i][j];  4.                        c