最少费用购物问题 动态规划

简单清晰的代码风格，完备的代码注释，详细的实验报告 算法分析。你值得拥有。 问题描述： 商店中每种商品都有标价。例如，一朵花的价格是2 元。一个花瓶的价格是5 元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销售。例如，3 朵花的价格不是6 元而是5 元。2 个花瓶加1 朵花的优惠价是10 元。设计一个算法，计算出某一顾客所购商品应付的最少费用。

#include
#include
#define N 5//每种商品的最大数量
#define B 5//最大商品种类数
#define S 99//最大的优惠组合数
#define C 999//最大的编号
//p104

/**
*B 0-5种商品
*K 0-5每种商品数量
*C 1-999商品编号
*P 1-999商品正常单价
*S 0-99 优惠组合
*定义五维数组 cost（abcde）表示购买商品 a b c d e 组合的最少花费
*/

int cost[N+1][N+1][N+1][N+1][N+1]={0};//cost（abcde）表示购买商品 a b c d e 组合的最少花费.从1开始
int offer[S][B+1];//优惠组合信息
//offer[Si][Bj]  Si组合中的Bj（从1开始）类商品的数量 offer[1..S][0]存储这种组合的花费

struct Purch
{
	int code;//编号
	int quatity;//要购买的数量
	int price;//单价
};

Purch purch[B];//定义购买物品信息数组

int product[B]={0};//存储当前已购买的商品数量

int num[C]={-1};//code编号的商品对应的在purch数组中的index

int b;//实际购买的商品种类

int s;//实际的优惠组合数

/*
*初始化数据
*/
void init（）
{
  FILE *input;
  FILE *offerFile;

  //***************************以下打开文件******************************************
  input=fopen（“input.txt““r“）;//open file

	if（input==NULL）//open file error
	{
		printf（“can‘t not open input.txt!\n“）;
		exit（1）;
	}

	offerFile=fopen（“offer.txt““r“）;

	if（offerFile==NULL）//open file error
	{
		printf（“can‘t not open offer.txt!\n“）;
		exit（1）;
	}
//*******************************读取数据并初始化***********************************************

	//置0初始化
	for（int i=0;i	{
		purch[i].code=-1;
		purch[i].price=0;
		purch[i].quatity=0;
	}

	for（i=0;i		for（int j=1;j<=B;++j）
		{
			offer[i][j]=0;
		}

	//读入文件数据
	fscanf（input“%d“&b）;//实际商品种类

	for（ i=0;i	{
       fscanf（input“%d %d %d“&purch[i].code&purch[i].quatity&purch[i].price）;//商品编码 数量 单价
	   num[purch[i].code]=i;
	}

	
	fscanf（offerFile“%d“&s）;//实际组合数
	for（i=0;i	{
		int pairs;//组合中的商品数
		fscanf（offerFile“%d“&pairs）;
		for（int j=0;j		{
			int c;//商品编号
			int n;//组合i中c编号商品的数量
			fscanf（offerFile“%d %d“&c&n）;
			offer[i][num[c]+1]=n;
		}

		fscanf（offerFile“%d“&offer[i][0]）;//组合的花费
	}

	//****************************以下关闭文件************************************************
	fclose（input）;
	fclose（offerFile）;
}

/**
*输出结果
*/
void printResult（）
{
	FILE *out=fopen（“output.txt““w“）;

	if（out==NULL）//open file error
	{
		printf（“can‘t not open output.txt to write!\n“）;
		exit（1）;
	}

	int mincost=cost[purch[0].quatity][purch[1].quatity][purch[2].quatity][purch[3].quatity][purch[4].quatity];
	printf（“minCost=%d\n“mincost）;
	fprintf（out“%d“mincost）;

}



/**
* 最小花费子问题求解
*/

void minCost（）
{
	int mincost=0;

	int quatity1;//已经购买的第一种商品的量
	int quatity2;
	int quatity3;
	int quatity4;
	int quatity5;

	for（int i=0;i	{
		mincost+=product[i]*purch[i].price;//将最小花费初始为没有优惠策略的花费
	}

	//对s种优惠政策依次讨论
	for（int j=0;j	{
		 quatity1=product[0]-offer[j][1];//第一种商品扣除当前优惠组合下的购买量的其它购买量
		 quatity2=product[1]-offer[j][2];
		 quatity3=product[2]-offer[j][3];
		 quatity4=product[3]-offer[j][4];
		 quatity5=product[4]-offer[j][5];

		if（quatity1>=0&&quatity2>=0&&quatity3>=0&&quatity4>=0&&quatity5>=0
			&&cost[quati

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      13449  2013-04-18 21:15  最少费用购物\Debug\MinCostShopping.obj

     文件      33792  2013-04-18 21:15  最少费用购物\Debug\vc60.idb

     文件      53248  2013-04-18 21:15  最少费用购物\Debug\vc60.pdb

     文件     196677  2013-04-18 21:15  最少费用购物\Debug\最少费用购物.exe

     文件     196196  2013-04-18 21:15  最少费用购物\Debug\最少费用购物.ilk

     文件     203604  2013-04-15 22:34  最少费用购物\Debug\最少费用购物.pch

     文件     467968  2013-04-18 21:15  最少费用购物\Debug\最少费用购物.pdb

     文件         15  2013-04-18 17:41  最少费用购物\input.txt

     文件       4044  2013-04-18 22:05  最少费用购物\MinCostShopping.cpp

     文件         24  2013-04-18 17:42  最少费用购物\offer.txt

     文件          2  2013-04-18 21:15  最少费用购物\output.txt

     文件       4359  2013-04-18 16:46  最少费用购物\最少费用购物.dsp

     文件        532  2013-04-15 21:24  最少费用购物\最少费用购物.dsw

     文件      41984  2013-04-18 22:05  最少费用购物\最少费用购物.ncb

     文件      49664  2013-04-18 22:05  最少费用购物\最少费用购物.opt

     文件       1329  2013-04-18 21:15  最少费用购物\最少费用购物.plg

     文件      26112  2013-04-18 22:04  张光裕_最少费用问题实验报告.doc

     目录          0  2013-04-18 21:15  最少费用购物\Debug

     目录          0  2013-04-18 22:05  最少费用购物

----------- ---------  ---------- -----  ----

              1292999                    19