Thread: 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?

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.

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

Originally Posted by viblic

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 ??

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?

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 ...

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.

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.