469,306 Members | 1,627 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,306 developers. It's quick & easy.

0-1 Knapsack Problem and the Greedy Algorithm

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:
Expand|Select|Wrap|Line Numbers
  1. // The "Knapsack" class.
  2. public class Knapsack
  3. {
  4.     public static void main (String[] args)
  5.     {   int n;
  6.     int nmax = 10;
  7.     int wmax = 85;
  8.     int w;
  9.     int addVal;  
  10.     int itemArray = new int [2][nmax];
  11.  
  12.     int solArray = new int [nmax][wmax];
  13.  
  14.     itemArray = {{10, 63, 84, 81, 33, 11, 67, 10, 65, 81}, { 9, 19, 5, 31, 48, 17, 46, 80, 38, 55}};
  15.  
  16.  
  17.     //This section of code fills the first row of the Solution Array
  18.     while(w <= wmax){
  19.  
  20.         if (itemArray [0][0] < w){
  21.         solArray[0][w] = itemArray[0][1];
  22.         }
  23.  
  24.         else solArray[0][w] = 0;
  25.  
  26.     }
  27.  
  28.  
  29.  
  30.      for (n = 1; n <= nmax-1; n++){
  31.  
  32.         for(w = 1; w <= wmax-1; w++){
  33.  
  34.             //checks to see if the item being looked at weighs more than the subproblem can carry
  35.             if (itemArray[0][n] > w){
  36.                 solArray[n][w] = solArray[n-1][w];
  37.             }
  38.  
  39.             //adds together the values of the previous subproblem and the current iteration of n
  40.             //and checks if it is of greater value than the previous row
  41.             addVal = solArray[n-1][w-itemArray[0][n]] + itemArray[1][n];
  42.             if (addVal > solArray[n-1][w]){
  43.             solArray[n][w] = addVal;
  44.             }
  45.  
  46.             //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              
  47.             else if (w >= itemArray[0][n] && solArray[n-1][w] < itemArray[1][n])
  48.             {solArray[n][w] = itemArray[1][n];}
  49.  
  50.             else solArray[n][w] = solArray[n-1][w];
  51.  
  52.  
  53.         }       
  54.     }
  55.  
  56.  
  57.     n = nmax-1;
  58.     w = wmax-1;
  59.     int includeArray = new int[i];
  60.     int i = 0;
  61.  
  62.     //populates a 1-dimensional array with the numbers of the items filling the knapsack in the optimal solution
  63.     while (n <= 0){
  64.         if ((solArray[n][w] != solArray[n-1][w]) && (solArray [n-1][w] != 0)){
  65.             includeArray[i] = n;
  66.             w = w - itemArray[0][n];
  67.             i++;
  68.         }
  69.  
  70.             n--;
  71.     }       
  72.  
  73.     includeArray.length = i;
  74.  
  75.     //print out solution array
  76.     for (n = 0; n <= nmax; n++){
  77.         for (w = 0; w <=wmax; w++){
  78.             System.out.println(solArray[n][w]);
  79.         }
  80.     }
  81.  
  82.     } // main method
  83. } // Knapsack class
P.S. NOOOOO, the forum messes with all my nice indentation!
Mar 7 '08 #1
7 10740
BigDaddyLH
1,216 Expert 1GB
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
Mar 7 '08 #2
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.
Mar 7 '08 #3
BigDaddyLH
1,216 Expert 1GB
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:
Expand|Select|Wrap|Line Numbers
  1. int[][] itemArray = {{10, 63, 84, 81, 33, 11, 67, 10, 65, 81}, { 9, 19, 5, 31, 48, 17, 46, 80, 38, 55}};
  2.  
Mar 7 '08 #4
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.
Mar 7 '08 #5
BigDaddyLH
1,216 Expert 1GB
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 ;-)
Mar 7 '08 #6
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?
Mar 7 '08 #7
BigDaddyLH
1,216 Expert 1GB
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
Mar 7 '08 #8

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

6 posts views Thread by Jack Smith | last post: by
12 posts views Thread by lothar | last post: by
5 posts views Thread by Koen | last post: by
3 posts views Thread by Frank | last post: by
8 posts views Thread by John Hazen | last post: by
6 posts views Thread by EXI-Andrews, Jack | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by suresh191 | last post: by
reply views Thread by harlem98 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.