//
#include “stdafx.h”
#include <stdio.h>
#include <stdlib.h>
#define INF 100000000
#define MAXNUM 10000
#define MONEYKIND 100
int n,S;
int V[MONEYKIND];
int min[MAXNUM],max[MAXNUM];
void dp(int*,int*);
//递推方法函数声明
void print_ans(int*,int);
//输出函数声明
//快速排序
int Partition (int r[],long first,long end)
{
float t;
while (first<end)
{
while (first<end&&r[first]<=r[end])end–;
if(first<end)
{
t=r[first];
r[first]=r[end];
r[end]=t;
first++;
}
while (first<end&&r[first]<=r[end])first++;
if(first<end)
{
t=r[first];
r[first]=r[end];
r[end]=t;
end–;
}
}
return first;
}
void QuickSort (int r[ ], int first, int end )
{
float pivotpos;
if(first<end){
pivotpos = Partition (r, first, end );
QuickSort (r,first,pivotpos-1);
QuickSort (r, pivotpos+1, end );
}
}
int main()
{
int i;
printf(“硬币的种数n(1-100):\n”);
n=4;
printf(“%d：\n”,n);
printf(“输入要组合的钱数S(0-10000):\n”);
scanf(“%d”,&S);
printf(“硬币种类：\n”);
V[1]=1;
V[2]=2;
V[3]=4;
V[4]=12;
for(i=1; i<=n; i++)
{
printf(“%d\t”,V[i]);
}
QuickSort(V,1,n);
dp(min,max);
printf(“\n”);
printf(“最小组合方案：\n”);
print_ans(min,S);
printf(“\n”);
/*printf(“最大组合方案：\n”);
print_ans(max,S);*/
system(“pause”);
return 0;
}
void dp(int *min,int *max)
//递推过程实现
{
int i,j;
min[0] = max[0] = 0;
for(i=1; i<=S; i++)//初始化数组
{
min[i]=INF;
max[i]=-INF;
}
for(i=1; i<=S; i++)
for(j=1; j<=n; j++)
if(i>=V[j])
{
if(min[i-V[j]]+1<min[i]){
min[i]=min[i-V[j]]+1;//最小组合过程
//printf(“%d\n”,min[i]);
}
if(max[i-V[j]]+1>max[i])
max[i]=max[i-V[j]]+1;//最大组合过程
}
}
void print_ans(int *d,int S)
//输出函数实现
{
int i;
for(i=1; i<=n; i++)
if(S>=V[i]&&d[S]==d[S-V[i]]+1)
{
printf(“%d-“,V[i]);
print_ans(d,S-V[i]);
break;
}
}