# 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.