471,829 Members | 1,861 Online

# 0-1 Knapsack Problem and the Greedy Algorithm 4
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;
10.     int itemArray = new int [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  < w){
21.         solArray[w] = itemArray;
22.         }
23.
24.         else solArray[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[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[n]] + itemArray[n];
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[n] && solArray[n-1][w] < itemArray[n])
48.             {solArray[n][w] = itemArray[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[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
8 20524 1,216 Expert 1GB

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
Tehcuod
4 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
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
Tehcuod
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
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
Tehcuod
4 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
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
DANILIN
21 16bit
Knapsack 0-1 & rosettacode & qbasic qb64 & WE

Classic Knapsack problem is solved in many ways

Contents: http://rosettacode.org/wiki/Knapsack_problem

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

Expand|Select|Wrap|Line Numbers
1. Open "knapsack.txt" For Output As #1
2. N=7: L=5: a = 2^(N+1): Randomize Timer 'knapsack.bas DANILIN
3. Dim L(N), C(N), j(N), q(a), q\$(a), d(a)
4.
5. For m=a-1 To (a-1)/2 Step -1: g=m: Do ' sintez shifr
6.     q\$(m)=LTrim\$(Str\$(g Mod 2))+q\$(m)
7.     g=g\2: Loop Until g=0
8.     q\$(m)=Mid\$(q\$(m), 2, Len(q\$(m)))
9. Next
10.
11. For i=1 To N: L(i)=Int(Rnd*3+1) ' lenght & cost
12. C(i)=10+Int(Rnd*9): Print #1, i, L(i), C(i): Next ' origin
13.
14. For h=a-1 To (a-1)/2 Step -1
15.     For k=1 To N: j(k)=Val(Mid\$(q\$(h), k, 1)) ' from shifr
16.         q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
17.         d(h)=d(h)+L(k)*j(k)
18.     Next
19.     If d(h) <= L Then Print #1, d(h), q(h), q\$(h)
20. Next
21. max=0: m=1: For i=1 To a
22.     If d(i)<=L Then If q(i) > max Then max=q(i): m=i
23. Next
24. 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:

Expand|Select|Wrap|Line Numbers
1.  1             2             17
2.  2             2             14
3.  3             2             17
4.  4             1             11
5.  5             2             18
6.  6             3             14
7.  7             3             10
8.
9.  5             73           1101000
10.  2             28           0100000
11.  5             81           0011100 !!!
12.  3             45           0011000
13.  5             76           0010010
14.  2             36           0000100
15.
16.  5             81           0011100
May 22 '22 #9

 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 3 posts views Thread by Van Dugall | last post: by 3 posts views Thread by amriksingh24 | last post: by reply views Thread by awasthiastha | last post: by reply views Thread by ComPDFKit | last post: by reply views Thread by Dimash Kudaiber | last post: by reply views Thread by antdb | last post: by reply views Thread by montazsy | last post: by reply views Thread by AndresCidInst | last post: by 1 post views Thread by guiromero | last post: by reply views Thread by aboka | last post: by 9 posts views Thread by CD Tom | last post: by reply views Thread by isladogs | last post: by