CODEWITHSUNDEEP
javarecursion
user3574854
user3574854

Reputation:

Recursive Dynamic Programming Knapsack Solution in Java

I have written this dynamic function to find maximum packed value for knapsack problem.

static int dyn(int maxItems, int maxSize)
    {
        if(maxItems < 0)
        {
            return 0;
        }
        if(tab[maxItems][maxSize] != -1)
        {

            return tab[maxItems][maxSize];
        }

        if( itemArray[maxItems].s > maxSize)
        {
            result =  dyn(maxItems-1,maxSize);
            return result;
        }
        else
        {
            result =  Math.max(dyn(maxItems-1, maxSize), dyn(maxItems-1, maxSize - itemArray[maxItems].s) + itemArray[maxItems].v);
            tab[maxItems][maxSize] = result;
            return result;
        }

    }

I'm calling this function from main as

int x = dyn(maxItems - 1, maxSize)

The itemArray structure is

public class Item {
 int v;
 int s;
}

Every time I'm getting 0 as an answer. Please tell me where I am going wrong

Upvotes: 2

Views: 385

Answers (1)

arunmoezhi
arunmoezhi

Reputation: 3200

Remove the if loop where you check tab[][] != -1. This will always be true and the actual knapsack recursion below it will never run. And I assume you populate the itemArray with items. Now this should work.

static int dyn(int maxItems, int maxSize)
{
    if(maxItems < 0)
    {
        return 0;
    }

    if( itemArray[maxItems].s > maxSize)
    {
        return dyn(maxItems-1,maxSize);
    }
    else
    {
        int result =  Math.max(dyn(maxItems-1, maxSize), dyn(maxItems-1, maxSize - itemArray[maxItems].s) + itemArray[maxItems].v);
        tab[maxItems][maxSize] = result;
        return result;
    }
}

Upvotes: 2

Related Questions