#include<stdio.h>
int main()
{
int n,C,d[10],i,j,V[15][15],b[15][15];
printf("enter maximum change");
scanf("%d",&C);
printf("enter no. of elements");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&d[i]);
}
for(i=0;i<=n;i++)
{
for(j=0;j<=C;j++)
{
if(i==0 || j==0)
{
//printf("A\n");
if(i==0)
V[i][j]=65535;
else
V[i][j]=0;
}
else if(j<d[i-1])
{
//printf("B\n");
V[i][j]=V[i-1][j];
b[i][j]=j;
}
else
{
//printf("C\n");
if(V[i-1][j]<((V[i][j-d[i-1]])+1))
{
V[i][j]=V[i-1][j];
b[i][j]=j;
}
else
{
V[i][j]=V[i][j-d[i-1]]+1;
b[i][j]=j-d[i-1];
}
}
//printf("%d %d %d\n",i,j,V[i][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=C;j++)
{
printf("%d ",V[i][j]);
}
printf("\n");
}
printf("\nminimum coins used is %d\n",V[n][C]);
i=n;
j=C;
while(j!=0)
{
if(V[i][j]==V[i-1][j])
i--;
else
{
printf("%d\t",d[i-1]);
j=b[i][j];
}
}
return 0;
}
int main()
{
int n,C,d[10],i,j,V[15][15],b[15][15];
printf("enter maximum change");
scanf("%d",&C);
printf("enter no. of elements");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&d[i]);
}
for(i=0;i<=n;i++)
{
for(j=0;j<=C;j++)
{
if(i==0 || j==0)
{
//printf("A\n");
if(i==0)
V[i][j]=65535;
else
V[i][j]=0;
}
else if(j<d[i-1])
{
//printf("B\n");
V[i][j]=V[i-1][j];
b[i][j]=j;
}
else
{
//printf("C\n");
if(V[i-1][j]<((V[i][j-d[i-1]])+1))
{
V[i][j]=V[i-1][j];
b[i][j]=j;
}
else
{
V[i][j]=V[i][j-d[i-1]]+1;
b[i][j]=j-d[i-1];
}
}
//printf("%d %d %d\n",i,j,V[i][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=C;j++)
{
printf("%d ",V[i][j]);
}
printf("\n");
}
printf("\nminimum coins used is %d\n",V[n][C]);
i=n;
j=C;
while(j!=0)
{
if(V[i][j]==V[i-1][j])
i--;
else
{
printf("%d\t",d[i-1]);
j=b[i][j];
}
}
return 0;
}
No comments:
Post a Comment