coin change program using dynamic programming knapsack with repetitions allowed

Question

I have written the below code to implement the coin change problem: you are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible.

I modified the knapsack with repetitions allowed problem by setting all the values of each coin to -1. The program should then return the maximum value such that the weight of the required coins(denominations) add up to the size variable(required change). I cannot figure where i have went wrong. I should be getting an answer of -2 implying i need two coins but i'm getting -1 as the answer. Code:

#include <stdio.h>
#define max(a,b) (a > b ? a : b)

int matrix[100][100] = {0};

int knapsack(int index, int size, int weights[],int values[]){
    int take,dontTake;

    take = dontTake = 0;

    if (matrix[index][size]!=0)
        return matrix[index][size];

    if (index==0){
        if (weights[0]<=size){
            matrix[index][size] = values[0];
            return values[0];
        }
        else{
            matrix[index][size] = 0;
            return 0;
        }
    }

    if (weights[index]<=size) 
        take = values[index] + knapsack(index, size-weights[index], weights, values); //knapsack(index) and not //knapsack(index-1) 

    dontTake = knapsack(index-1, size, weights, values);

    matrix[index][size] = max (take, dontTake);

    return matrix[index][size];

}

int main(){
    int nItems = 4;
    int knapsackSize = 10;
    int weights[4] = {5,4,6,3};
    int values[4] = {-1,-1,-1,-1};

    printf("Max value = %dn",knapsack(nItems-1,knapsackSize,weights,values));

    return 0;
}

Where am i going wrong and how can i fix this?

Besides that you should run in a debugger, and step through the code line by line to see when and where it doesn't to what it's supposed to do. It's hard work debugging a program like this, but also something all programmers have to do and know how to do. — Some programmer dude
You need to try to narrow down the problem. If you understand how the algorithm works, you should be able to pinpoint where in the execution it does something unexpected. If you don't understand how the algorithm works, then you need to describe what you don't understand specifically. — Vaughn Cato
How are you using the matrix (what's the first index, what's the second index?), what do the weights mean and what do the values mean? — MicroVirus
The matrix is basically used to store the already computed values. Index is the number of items we can still pick. Size denotes the amount of unused weight or amount of change not yet accounted for. The weights array gives the denomination value of each coin. The value array gives a value to each type of coin and in this case the value of each coin is -1 because it doesn't matter which coins we take. What matters is the number of coins. — RaviTej310

uSeemSurprised uSeemSurprised · Accepted Answer · 2016-03-10T14:26:53

It is simple because, -1 > -2 and you are taking the maximum between the 2 choices at every level.

EDIT : I have impelmented a solution in which values are taken as positive, also i have made minor changes to the code, if there is something that you do not understand feel free to ask.

#include <stdio.h>
#define min(a,b) (a < b ? a : b)
#define INF 10000000

int matrix[100][100] = {0};

int knapsack(int index, int size, int weights[],int values[]){
    int take = INF;

    if (index == -1){
        if(size == 0) return 0;
        else return INF;
    }

    if (matrix[index][size]!=-1)
        return matrix[index][size];

    for(int itemcount = 0;(itemcount * weights[index]) <= size;itemcount++){
        if ((weights[index] * itemcount) <= size) 
            take = min(take, (values[index] * itemcount) + knapsack(index - 1, size - (itemcount * weights[index]), weights, values)); //knapsack(index) and not //knapsack(index-1) 
    }

    matrix[index][size] = take;

    return matrix[index][size];

}

int main(){
    int nItems = 4;
    int knapsackSize = 10;
    int weights[4] = {5,4,6,3};
    int values[4] = {1,1,1,1};
    for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) matrix[i][j] = -1;

    printf("Min value = %d\n",knapsack(nItems-1,knapsackSize,weights,values));

    return 0;
}

Link to solution on Ideone : http://ideone.com/TNycZo

Here i have taken infinity as a large integer, to find minimum values, if the answer is infinity that means it is not possible to create such a denomination.

coin change program using dynamic programming knapsack with repetitions allowed

1 Answers