0-1 Knapsack Problem and the Greedy Algorithm

[Tehcuod]

Ok, so, for those of you that are unfamiliar with the 0-1 Knapsack problem, I have to write an to take the weights and corresponding values of 10 items, and find which items to put in a knapsack that holds 85 pounds to have the maximum value in the knapsack.

I keep getting compiler errors, and quite honestly, I'm really bad at debugging.

Code:

// The "Knapsack" class.
public class Knapsack
{
    public static void main (String[] args)
    {   int n;
    int nmax = 10;
    int wmax = 85;
    int w;
    int addVal;  
    int itemArray = new int [2][nmax];
 
    int solArray = new int [nmax][wmax];
 
    itemArray = {{10, 63, 84, 81, 33, 11, 67, 10, 65, 81}, { 9, 19, 5, 31, 48, 17, 46, 80, 38, 55}};
 
 
    //This section of code fills the first row of the Solution Array
    while(w <= wmax){
 
        if (itemArray [0][0] < w){
        solArray[0][w] = itemArray[0][1];
        }
 
        else solArray[0][w] = 0;
 
    }
 
 
 
     for (n = 1; n <= nmax-1; n++){
 
        for(w = 1; w <= wmax-1; w++){
 
            //checks to see if the item being looked at weighs more than the subproblem can carry
            if (itemArray[0][n] > w){
                solArray[n][w] = solArray[n-1][w];
            }
 
            //adds together the values of the previous subproblem and the current iteration of n
            //and checks if it is of greater value than the previous row
            addVal = solArray[n-1][w-itemArray[0][n]] + itemArray[1][n];
            if (addVal > solArray[n-1][w]){
            solArray[n][w] = addVal;
            }
 
            //if only the current item can be fit in the knapsack, checks if the item is more valuable than the value in the row above              
            else if (w >= itemArray[0][n] && solArray[n-1][w] < itemArray[1][n])
            {solArray[n][w] = itemArray[1][n];}
 
            else solArray[n][w] = solArray[n-1][w];
 
 
        }       
    }
 
 
    n = nmax-1;
    w = wmax-1;
    int includeArray = new int[i];
    int i = 0;
 
    //populates a 1-dimensional array with the numbers of the items filling the knapsack in the optimal solution
    while (n <= 0){
        if ((solArray[n][w] != solArray[n-1][w]) && (solArray [n-1][w] != 0)){
            includeArray[i] = n;
            w = w - itemArray[0][n];
            i++;
        }
 
            n--;
    }       
 
    includeArray.length = i;
 
    //print out solution array
    for (n = 0; n <= nmax; n++){
        for (w = 0; w <=wmax; w++){
            System.out.println(solArray[n][w]);
        }
    }
 
    } // main method
} // Knapsack class

P.S. NOOOOO, the forum messes with all my nice indentation!

[BigDaddyLH]

Please enclose your posted code in [code] tags (See How to Ask a Question).

This makes it easier for our Experts to read and understand it. Failing to do so creates extra work for the moderators, thus wasting resources, otherwise available to answer the members' questions.

Please use [code] tags in future.

MODERATOR

[Tehcuod]

Please enclose your posted code in [code] tags (See How to Ask a Question).

This makes it easier for our Experts to read and understand it. Failing to do so creates extra work for the moderators, thus wasting resources, otherwise available to answer the members' questions.

Please use [code] tags in future.

MODERATOR

Heh, thanks! I apparently need to learn to read.

[BigDaddyLH]

Well, knowing syntax is a prerequisite for programming. It's not debugging. Anyhowdy, I'll get you started: the syntax used to assign to an array variable can only be used to initialize an array:

int[][] itemArray = {{10, 63, 84, 81, 33, 11, 67, 10, 65, 81}, { 9, 19, 5, 31, 48, 17, 46, 80, 38, 55}};
 

[Tehcuod]

Ah, thanks, I'm kinda rusty on my arrays, and Java in general... and for some reason I couldn't figure out the syntax for that.

[BigDaddyLH]

Ah, thanks, I'm kinda rusty on my arrays, and Java in general... and for some reason I couldn't figure out the syntax for that.

I left a few syntax errors for you to fix ;-)

[Tehcuod]

I left a few syntax errors for you to fix ;-)

Ok, well, one thing I've been having issues with that I'm sure isn't right is with my includeArray[]

How does one go about handling an array that they don't know the length of until the while loop below has been iterated through?

[BigDaddyLH]

Ok, well, one thing I've been having issues with that I'm sure isn't right is with my includeArray[]

How does one go about handling an array that they don't know the length of until the while loop below has been iterated through?

The best way is not to use arrays at all. I seldom use arrays, apart from trivial uses. Use an appropriate collection class:

http://java.sun.com/docs/books/tutor...ons/index.html

[DANILIN]

Knapsack 0-1 & rosettacode & qbasic qb64 & WE

Classic Knapsack problem is solved in many ways

Contents: http://rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1

My newest program synthesizes all ciphers from 0 & 1
adding an extra register and 0 remain on left in cipher

Number of comparisons decreases from N! to 2^N
for example N=5 N!=120 >> 2^N=32

Random values origin are automatically assigned
quantity and quality and integral of value is obtained
and in general: integral of quantity and quality
and it is possible to divide only anyone will not understand

Program write results to qb64 directory

Open "knapsack.txt" For Output As #1
N=7: L=5: a = 2^(N+1): Randomize Timer 'knapsack.bas DANILIN
Dim L(N), C(N), j(N), q(a), q$(a), d(a)
 
For m=a-1 To (a-1)/2 Step -1: g=m: Do ' sintez shifr
    q$(m)=LTrim$(Str$(g Mod 2))+q$(m)
    g=g\2: Loop Until g=0
    q$(m)=Mid$(q$(m), 2, Len(q$(m))) 
Next
 
For i=1 To N: L(i)=Int(Rnd*3+1) ' lenght & cost
C(i)=10+Int(Rnd*9): Print #1, i, L(i), C(i): Next ' origin
 
For h=a-1 To (a-1)/2 Step -1
    For k=1 To N: j(k)=Val(Mid$(q$(h), k, 1)) ' from shifr
        q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
        d(h)=d(h)+L(k)*j(k)
    Next
    If d(h) <= L Then Print #1, d(h), q(h), q$(h)
Next
max=0: m=1: For i=1 To a
    If d(i)<=L Then If q(i) > max Then max=q(i): m=i
Next
Print #1,: Print #1, d(m), q(m), q$(m): End

Main thing is very brief and clear to even all

Results is reduced manually:

 1             2             17 
 2             2             14 
 3             2             17 
 4             1             11 
 5             2             18 
 6             3             14 
 7             3             10 
 
 5             73           1101000
 2             28           0100000
 5             81           0011100 !!!
 3             45           0011000
 5             76           0010010
 2             36           0000100
 
 5             81           0011100