Saturday, January 21, 2012

Coin Change ( Minimum coin change but use only at once a coin no repetation.)

#include <iostream>
#include <vector>
using namespace std;


#define SIZE 20020
#define INF 1000000


int dp[SIZE],coin[SIZE];


int generate(int n,int m);


int main()
{
    int test,i,n,m;


    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n); //target point
        scanf("%d",&m);
        for(i=0;i<m;i++)
            scanf("%d",&coin[i]);
        generate(n,m);
    }
}


int generate(int n,int m)
{
    int i,j,high;


    for(i=0;i<SIZE;i++)
        dp[i]=INF;


    dp[0]=0;


    high=0;
    for(i=0;i<m;i++)
    {
        for(j=n;j>=0;j--)
        {
            dp[j+coin[i]]=min(dp[j]+1,dp[j+coin[i]]);
        }
    }
    if(dp[n]!=INF)
        printf("Minimum Coin:%d\n",dp[n]);
    else printf("Impossible\n");
}

No comments:

Post a Comment