#include <stdio.h>
#include <string.h>
#define MAX 10000
char dyn[MAX]={1};
char nnom[MAX];
int how[MAX];
char len[MAX];
void main()
{
puts("Enter money (<10000):");
int m,i,j;
scanf("%d",&m);
int noms[100],nnoms=-1,t;
do{
printf("Enter nominal (or 0 to finish): ");
scanf("%d",&noms[++nnoms]);
}while(noms[nnoms]);
for(i=0;i<nnoms;i++)
for(j=1;j<=nnoms-i;j++)
if(noms[j-1]<noms[j])
{
t=noms[j-1];
noms[j-1]=noms[j];
noms[j]=t;
}
i=0;
while(i<nnoms)
{
for(j=0;j<m;j++)
if(dyn[j])
if(j+noms[i]<=m)
if(!dyn[j+noms[i]]||len[j]+1<len[j+noms[i]])
{
dyn[j+noms[i]]=1;
how[j+noms[i]]=j;
nnom[j+noms[i]]=i;
len[j+noms[i]]=len[j]+1;
}
i++;
}
if(!dyn[m])puts("Really can't exchange...");
else
{
puts("Using following row:");
while(m)
{
printf("%d ",noms[nnom[m]]);
m=how[m];
}
}
} |
