money.cpp

这是暑假写的最少硬币问题算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <math.h>

#define   MAX  10000
#define     N    100

int n,price;
int s[N],v[N];

int  money(){

	int i,j;
	s[0]=0;
	if(v[1]==1)
		s[1]=1;
	else s[1]=MAX;

	for(i=2;i<=price;i++){
		s[i]=MAX;
		for(j=1;j<=n;j++)
			if(i-v[j]>=0&&1+s[i-v[j]]<s[i])
				s[i]=1+s[i-v[j]];

	}

	return s[price];

}

void main(){

	int i,result;
	FILE *fp;

	if((fp=fopen("lizi.txt","r"))==NULL){
		printf("can not open lizi.txt!\n");
		exit(0);
	}

	fscanf(fp,"%d",&price);
	fscanf(fp,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(fp,"%d",&v[i]);
	fclose(fp);
	result=money();

	printf("最少硬币数为:%d\n",result);

}