0
import java.util.ArrayList;

class Knapsack
{

// A utility function that returns maximum of two integers
static 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
static int knapSack(int W, int wt[], int val[], int n, ArrayList<Integer> iteration)
{

    int i, w;
    int K[][] = new int[n+1][W+1];

    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            // add 1 to count up the iterations.
            iteration.add(1);
            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];
}


// Driver program to test above function
public static void main(String args[])
{
    // 16 items
    int Weights[] = {1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};
    int Values[] = { 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };

    // Max weight 
    int  W = 20;

    // number of item which is 16
    int n = Values.length;

    // Count up the iteration 
    ArrayList<Integer> iteration = new ArrayList<Integer>();

    // Will print out the Max value result. 
    System.out.println(knapSack(W, Weights, Values, n, iteration));
    // returns 280

    // Should print out the number of iteration.
    System.out.println(iteration.size());
    // returns 357

  }

/*This code is contributed by Rajat Mishra */
}

Hello! This is my first questions to StackOverflow, Hope it is not a duplicated question.

The code above is originally from here. I made a slight change to find out how many iterations needed to solve the problem.

Dynamic programming algorithm for Knapsack problem should give a time complexity of O(nW), When n is the number of items and W is the capacity of the knapsack.

But The algorithm returns iterations of 357. Because I thought, since

  • n = 16
  • W = 20

Thus, It should give 320 iterations.

Can anybody explain what's wrong with this?

  1. The code is wrong
  2. Time complexity doesn't always match to the result.
Dennis Lee
  • 23
  • 3
  • The complexity is in Big-Oh notation, So shouldn't the real result(357) be lower than BIg-Oh(320)? – Dennis Lee Dec 17 '17 at 09:31
  • Could you use smaller input sizes and debug the code by putting onto paper what you would expect and then see what the code is doing? – Nico Haase Dec 17 '17 at 09:43
  • Big-O ignores constant factors, so you can't compare the number of iterations like this. Whether the code is actually correct or how to fix it is something you'll need to figure out yourself through testing and [debugging](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) though. – Bernhard Barker Dec 17 '17 at 09:52
  • Thanks for helpful comment! @Dukeling That's what i should do. I'll be back with an answer. – Dennis Lee Dec 18 '17 at 13:25

0 Answers0