#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