C Solution with Knapsack DP Explanation


  • 0
    R
    This program is unbounded version of Knapsack Problem. Here we have to find the minimum number of coins using which we can make our resultant amount. We make an array of size as total amount. The ith value will store the minimum number of coins used to get amount equal to i and if its not possible to get sum i, value will be zero.
    
    num of coins needed to get sum i = min of (num of coins till now, num of coins to get [i-coin(j)] + 1)
    a[i] = min( a[i], a[i-c[j]]+1)
    
    int coinChange(int* c, int aS, int N) {
        int i, j, *a;
        if(N == 0) return 0;
        a = malloc(sizeof(int)*(N+1));
        a[0] = 0;
        for(i=1; i<=N; i++)
        {
            a[i] = 0;
            for(j=0; j<aS; j++)
            {
                if(c[j] > i)		// skip if coin value is more than i
                    continue;
                else if(i==c[j])	// coin value is equal to i so only 1 is needed to get sum i
                {
                    a[i] = 1;
                    break;
                }
                else if(a[i-c[j]] == 0)	// skip if amount(i-coin(j)) is zero which means we cannot achieve amount(i-coin(j))
                    continue;   
                if(a[i])	//	update a[i] if its value is 0 else use minimum of a[i] or a[i-coin[j]]+1 (+1 is for including jth coin)
                    a[i] = a[i] > a[i-c[j]]+1 ? a[i-c[j]]+1 : a[i];
                else
                    a[i] = a[i-c[j]]+1;
            }
        }
        i = a[N] ? a[N] : -1;
        free(a);
        return i;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.