CODEWITHSUNDEEP
calgorithmdynamic-programmingknapsack-problem
Kraken
Kraken

Reputation: 24243

Is there something wrong with my knapsack

I have a knapsack sort of problem wherein, My constraints are that

  1. Maximum money can not be exceeded
  2. Input array of cost and weight, ie cost of item i and weight of item i
  3. Maximize the weight.

My Input and Output are supposed to be of the following nature

3 4 //3 is the number of different Items, 4 is the maximum money, next three lines show cost and weight

2 1 // cost and weight

2 2 // cost and weight

3 5 // cost and weight

Output of the above would be 5

Below is my solution, the codechef says I am getting a wrong answer, can anyone help me what could be the possible cause for that?

Apart from that, is there something wrong with my approach and can I do any better. I looked up the solution from here and it seems to me that I have got most of it correct.

Thanks.

#include<stdio.h>
#include<stdlib.h>
int max(int a,int b){
    return a > b ? a : b;
}

int findOutput(int maxMoney,int index,int numOfItems,int *cost,int *weight, int **output){
    if(index >= numOfItems)
        return 0;
    if(maxMoney < cost[index])
        return 0;
    if(output[maxMoney][index] != 0)
        return output[maxMoney][index];
    int a = findOutput( maxMoney-cost[index],index+1,numOfItems,cost,weight,output) + weight[index];
    int b = findOutput(maxMoney,index+1,numOfItems,cost,weight,output);
    output[maxMoney][index] = max(a,b);
    return output[maxMoney][index];
}

int main(){
    int outputFinal = findOutput(maxMoney,0,numOfItems,cost,weight,output);
}

Upvotes: 1

Views: 214

Answers (1)

Vikram Bhat
Vikram Bhat

Reputation: 6246

The problem in the code seems to be :-

 if(maxMoney < cost[index])
        return 0;

here you are returning that no items after current item cannot fit in the knapsack but there might be a item that has cost smaller than maxMoney.

Remove the above statement and do following modification :-

int findOutput(int maxMoney,int index,int numOfItems,int *cost,int *weight, int **output){
    if(index >= numOfItems)
        return 0;
    if(output[maxMoney][index] != -1)
        return output[maxMoney][index];
    int a = 0;  
    if(maxMoney >= cost[index]) {
     a = findOutput( maxMoney-cost[index],index+1,numOfItems,cost,weight,output) + weight[index]; }
    int b = findOutput(maxMoney,index+1,numOfItems,cost,weight,output);
    output[maxMoney][index] = max(a,b);
    return output[maxMoney][index];
}

Check only while calculating a if maxMoney is greater than or equal to cost of item so that there is a chance to include the item else that case will have zero value.

Note :- Dont use zero as sentinel values for memoization try negative (-1) because there can be cost of zero but negetive is impossible.

Upvotes: 2

Related Questions