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!
8 20524
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
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.
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}};
-
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.
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 ;-)
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?
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
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
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
| | | | | | | | | | | | | |