CODEWITHSUNDEEP
algorithmdynamicknapsack-problem
Caleb Bolton
Caleb Bolton

Reputation: 21

0-1 knapsack dynamic programming solution does not work

This is the 0-1 knapsack problem dynamic programming code found on geeks for geeks. I've changed the input for my own test, but it doesn't seem to work. Wouldn't the optimal solution be 1 of item 4 (v:10, w:7) and 3 of item 1 (v:1, w:1) adding up to 13? When I run the code and do the algorithm by hand it turns out to be 12 with items 2 and 4. Where am I going wrong?

// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];

// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
    for (w = 0; w <= W; w++)
    {
        if (i==0 || w==0)
            K[i][w] = 0;
        else if (wt[i-1] <= w)
            K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
        else
            K[i][w] = K[i-1][w];
    }
}

return K[n][W];
}

int main()
{
    int val[] = {1, 2, 5, 10};
    int wt[] = {1, 3, 4, 7};
    int W = 10;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Upvotes: 2

Views: 328

Answers (1)

MBo
MBo

Reputation: 80187

Because this algorithm solves 0-1 Knapsack problem.

In this formulation only one instance of every item is available. That is why solution uses items once.

(perhaps you was thinking about knapsack with unlimited (or restricted) quantity for every item)

Upvotes: 1

Related Questions