Knapsack problem

This is a discussion on Knapsack problem within the C Programming forums, part of the General Programming Boards category; I have a problem like this (knapsack type of problem): I have an array of these values. Code: table [16] ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    8

    Knapsack problem

    I have a problem like this (knapsack type of problem): I have an array of these values.

    Code:
    table [16] = { 0, 1, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53 }
    Given an index, I have to divide that into smaller pieces, such that the sum of their contents is the largest possible.

    So say, an index of 3 corresponds to the value 0. But if I take the values of index 1 and 2 (3 total) it would then correspond to a value of 1+7 which is the largest possible.

    This is what I have so far

    Code:
    int knapSack ( int index, int * array, int arrayLen )
    {
        int j, i;
        int min;
        int sum = 0;
    
        findMin(array, arrayLen, &min);
    
        for (i=arrayLen-1; i>=1; i-=1)
        {  
            if (min*i <= array[i])
            {
                for (j=index; j>=i; j-=i)
                {
                    sum+=array[i];
                    
                    if (j-i <= i) 
                        index = j-i;
                    
                    if (j==0 && i==0) 
                        continue;
                }
            }
            
            if (min == array[i])
            {
                for (j=index; j>=i; j-=i)
                {
                    sum+=array[i];
                    
                    if (j-1 <= i)
                        index = j-i;
                    
                    if (j==0 && i==0) 
                        continue;
                }
            }
        } 
        return sum;    
    }
    However this algorithm falls for a the value of 16. It gives me the value of 15+1 (54), however the optimal solution is the value of 2*8 (56) ... Any ideas on the algorithm?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Welcome to the forum, Viblic!

    I'm unable to help with your problem, however. The description has left me with more questions than answers, but others might well sort it out.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    8
    I know the description was not the best possible, however I'll try to give a smaller instance of the problem, so that you can help me out.

    I have a table like this

    0 1 2 (indices of the array)
    0 4 5 (contents of the array)

    I need to find the largest summation of the contents for a given number which corresponds to an index of the array.

    For example, for number 2 I could have the content of array[2] which is 5 or I could have twice the content of array[1] which is 4+4.

    Obviously, since 8 is bigger than 5, 8 is the optimal solution ... I hope I was clearer this time.

    Thanks anyway

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by viblic View Post
    I know the description was not the best possible, however I'll try to give a smaller instance of the problem, so that you can help me out.

    I have a table like this

    0 1 2 (indices of the array)
    0 4 5 (contents of the array)

    I need to find the largest summation of the contents for a given number which corresponds to an index of the array.

    For example, for number 2 I could have the content of array[2] which is 5 or I could have twice the content of array[1] which is 4+4.

    Obviously, since 8 is bigger than 5, 8 is the optimal solution ... I hope I was clearer this time.

    Thanks anyway
    The 4+4 is the part that confuses me. Why the 2 times?

    There's a 0, a 4, and a 5, and you have a summation that totals to 8 ??

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    8
    Consider the indices as if they were coins and the contents as if they were objects you can buy.

    So
    0 coins --> 0 objects
    1 coins --> 4 objects
    2 coins --> 5 objects

    If I had 2 coins I could buy 5 objects instantly or I could divide them 1+1, so buy 4 objects + 4 objects ....

    Any clearer now?

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    That got it! (thanks).

    The last valid index is 15 (0 to 15 is 16). So it should fail with 16 - your program is out of bounds of the array.
    Last edited by Adak; 12-04-2011 at 12:51 PM.

  7. #7
    Registered User
    Join Date
    Nov 2011
    Posts
    8
    Yeah right but the loop only iterates from 1 to 16-1.

    for(i=arrayLen-1; i>=1; i--)

    Moreover if I reach the outside bounds, it means I should divide it into valid array bounds such as 15+1, 14+2 or whatever produces the optimal value ...

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    For things like this, I find the simplest input that shows the error, and then run it with added printf() and getchar() lines inside the loops, to show me what they hey is going on. By all means use a debugger and watch your values as you loop through the code, also.

    Determine what the sub sums should be before you run it, calculating them by hand. Then watch for the first sub sum in your program, that doesn't match that value.

    Yes, it's time consuming.

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    8
    Adak, thank you very much for your replies, time and effort. I appreciate this and I mean it.

    Certainly, I posted this because there was a problem with it, however, the above program does what it was meant to do because the algorithm was designed as such. Even if I were to do hand calculations with this algorithm I would get the same results. There was no pitfall in the program itself, just in the idea behind it.

    Just for the record, I solved this by using recursion and testing all possible solutions. It is considerable slower but I'm getting the right result however. Once again, thanks for you help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 0-1 knapsack problem
    By madennn in forum C Programming
    Replies: 2
    Last Post: 03-29-2011, 08:08 AM
  2. knapsack problem?
    By nimitzhunter in forum General Discussions
    Replies: 7
    Last Post: 01-28-2011, 01:16 PM
  3. knapsack problem ?
    By nmt1402 in forum C Programming
    Replies: 1
    Last Post: 01-26-2011, 07:33 PM
  4. knapsack problem
    By fnfn in forum C++ Programming
    Replies: 1
    Last Post: 07-19-2007, 04:14 PM
  5. Knapsack Problem
    By Fork in forum C Programming
    Replies: 4
    Last Post: 11-13-2006, 12:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21