dfffff.cpp

问题描述 设有n种不同面值的硬币

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int min(int a,int b)
{
	if(a > b)
		return b;
	else
		return a;
}

int find(vector<int> c,int j)
{

	int moneys = 0;

	if(j <= 0)
		return moneys;
	int size = c.size();

	if(size == 1)
	{
		if(j%c[0] == 0)
			moneys += j/c[0];
		else
			moneys += 10000000;

		return moneys;
	}

	
	if(j >= 0 && j < c[size-1])
	{
		c.pop_back();
		moneys += find(c,j);
		return	moneys;
	}
		
	else
	{

		int b = find(c,j-c[size-1]) + 1;

		c.pop_back();

		int a = find(c,j);
		
		if(a > b)
		{
			moneys += b;			
			return moneys;		
		}	
		else
		{
			moneys += a;
			return moneys;
		}	
	}

	
}



void main()
{
	int number;
	vector<int> cs;
	int money;
	int temp;
	ifstream infile("in.txt");

	while(!infile)
	{
		cerr << "can not open the in file!" << endl;
	}

	infile >> number;

	for(int i = 0; i < number; i++)
	{
		infile >> temp;
		cs.push_back(temp);

	}

	infile >> money;

	int s = find(cs,money);

	cout << "s  : " << s <<  endl;


}