用贪心算法实现购物找零支付+找零使用最少硬币数

硬币找钱问题 问题描述 设有6种不同面值的硬币，各硬币的面值分别为5分，1角，2角，5角，1元，2元。现要用这些面值的硬币来购物和找钱。购物时规定了可以使用的各种面值的硬币个数。 假定商店里各面值的硬币有足够多，顾客也可用多种方式支付。在1次购物中希望使用最少硬币个数。例如，1次购物需要付款0.55元，没有5角的硬币，只好用2*20+10+5共4枚硬币来付款。如果付出1元，找回4角5分，同样需要4枚硬币。但是如果付出1.05元（1枚1元和1枚5分），找回5角，只需要3枚硬币。这个方案用的硬币个数最少。 您的任务：对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。 输入 有若干行测试数据。每一行有6个整数a5、a4、a3、a2、a1、a0和1个有2位小数的实数money，分别表示5分，1角，2角，5角，1元，2元面值的硬币个数和付款金额，money<=1000。文件以6个0结束（不必处理）。 输出 对每一行测试数据，一行输出最少硬币个数。如果不可能完成交易，则输出“impossible”。 输入样例 2 4 2 2 1 0 0.95 2 4 2 0 1 0 0.55 0 0 0 0 0 0 输出样例 2 3

#include 
#include 
using namespace std;


int coins[6];//各面值硬币数
int count=0;//需要的最少硬币数
int costc[6]={ 5 102050100200};//需支付数和硬币面值以分计算
ifstream input（“input.txt“） ;
ofstream output（“output.txt“）;
void getData（）
{

	for（int i=0;i<6;i++）
	{
		input>>coins[i];
		
	}
	double costt;
	input>>costt;
	cost=（int）（costt*100）;//将输入的钱转为 分

	cout<		for（ i=0;i<6;i++）
	{
	cout<	}
}

int contains（int a）
{
	for（int i=0;i<6;i++）
	{
		if（c[i]==a&&coins[i]>0）return i;
	}
	return -1;
}

void getMinCount（）
{
	for（int i=5;i>=0;i--）
	{
		if（coins[i]>0）
		{	int *cc=（int *）malloc（（i+1）*sizeof（int））;//开辟新数组来保存虚拟币值的数量
	    	cc[0]=0;
			for（int k=1;k			{
				cc[k]=c[k-1];
			}
			for（int j=0;j<1+i;j++）
			{
		
				if（cost>=（c[i]-cc[j]））
				{
					if（coins[i]>=cost/（c[i]-cc[j]））//当前面值硬币如果足够支付余额
					{	count+=cost/（c[i]-cc[j]）+1;
				
						if（contains（c[i]-cc[j]）!=-1）
						{
							count--;//如果消费者具有该硬币，则无需使用找零，因为找零需要耗费2个硬币，而支付只需要一个硬币
							coins[contains（c[i]-cc[j]）]-=cost/（c[i]-cc[j]）;//相应硬币数减少
						}
						else coins[i]-=cost/（c[i]-cc[j]）;//找零法相应硬币数减少
					//	cout<						cost=cost%（c[i]-cc[j]）;	
						if（contains（c[i]）==-1）break;//如果该硬币用完，无需继续计算，用下一个小面值的吧
					}
					else //如果当前币值不够支付，则用完该币值
					{
						count+=coins[i];
						cost=cost-c[i]*coins[i];
						coins[i]=0;
					}
				
				 
				}

			}
		}

	}

	if（count==0||cost!=0）{cout<	else
	{
		cout<		for（ i=0;i<6;i++）
		{
			cout<		}
		cout<	}
	
}


void main（）
{
	while（!input.eof（））
	{
		count=0;
		getData（）;
    	getMinCount（）;
	}
	input.close（）;
	output.close（）;


}

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

     文件         82  2011-04-07 10:15  input.txt

     文件       2136  2011-04-07 10:42  4-3.cpp

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

                 2218                    2