Demo entry 6657128

15840148835

   

Submitted by anonymous on Nov 02, 2017 at 14:45
Language: C++. Code size: 1.0 kB.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include "file.h"

using namespace std;
#define INF 999999

int FindMin(int money,int *coin, int n)
{
	int *coinNum = new int[money+1]();//储存子问题的最优解
	int *coinValue = new int[money+1]();//记录所使用的硬币
	coinNum[0]=0;
	for(int i = 1;i <= money;i++)
	{
		int minNum = INF;
		int usedMoney = 0;//这次找零,在原来的基础上需要的硬币
		for(int j = 0;j < n;j++)
		{
			if(i >= coin[j])
			{
				//需要判断i-coin[j]是否能找的开,如果找不开,就不需要更新。
				if( coinNum[i-coin[j]]+1 < minNum&&(i == coin[j]||coinValue[i-coin[j]] != 0))
				{
					minNum = coinNum[i-coin[j]]+1;
					usedMoney = coin[j];
				}
			}
		}
		coinNum[i] = minNum;
		coinValue[i] = usedMoney;
	}
	if(coinValue[money]==0)
		return -1;
	else
		return coinNum[money];
	delete []coinNum;
	delete []coinValue;
}
int main()
{
	int num[200] = {0};
	int len = 0;
	len = FileR_int(num);
	int coin[13];
	for (int i = 0;i < num[0];i++){
		coin[i] = num[i+1];
	}
	int Money = num[len-1];
	FileW_int(FindMin(Money,coin,num[0]));
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).