knapsack, towers of hanoi, v. stuck!

[mike rivers]

hey all, you probably get this sort of thing all the time. i've been working pretty hard on this. i've joined a course late, and i have to complete this exercise. i am still very lost in the world of java. if anyone can help it will be greatly appreciated. code, suggestions, reading topice etc....
the knapsack:
knapsack can hold 35kg
have 20 objects with random weights (1-5kg) and random value ($1-10)
object:given the knapsack can hold upto 20 objects. maximise the total value of the contents of the knapsack.
the towers of hanoi:
three pins, a,b,c
three disks 1,2,3 initially placed on pin a, with 1 ontop of 2 and 2 on 3
disk 1 is the smallest, then 2, and the largest is disk 3
object nly 1 disk can move at a time, they must all end up on pin 3 in the same order as the starting order. only a smaller disk can be placed on a larger one. solve
email: [email protected]

[Dirk Schreckmann]

Welcome to JavaRanch, mike!
How have you thought to begin to solve either of these problems?

[Junilu Lacar]

here are some tips for solving the tower of hanoi:
- The problem can be solved by breaking down the large task (moving the entire tower) into progressively smaller tasks until you arrive at a trivial task that can be easily solved. To move a tower with N disks (disk 0 being the smallest and N the largest) from peg 1 to peg 3, the first breakdown would be to move the subtower consisting of disks 0 - (N-1) to peg 2, move disk N to peg 3, then move the subtower from peg 2 to peg 3. Now since the subtower consists of more than one disk, it is non-trivial and you need to break it down the same again. You keep breaking down the task until the subtower consists of only one disk, the trivial problem, and then you're done! The easiest way to solve this is by using a recursive function. Some monks in Tibet have supposedly been playing this game for centuries (they have to move 64 disks) and when they are done, it will be the end of the world :roll:
- assign the pegs numbers 1, 2, & 3. Doing so allows you to calculate the "using" peg -- as in move tower "from" peg X "to" peg Y "using" peg Z as a temporary holding peg for the subtower. So, given "from" and "to", you can calculate "using" by:
using = 6 - from - to
For example, if you need to move a tower (or subtower) from peg 1 to peg 3, using = 2. If you need to move a (sub)tower from peg 2 to peg 1, using = 3 and so on. If you don't use this scheme, you'll have to use a series of if statements to get the "using" peg number.
The real challenge here though is animating it so you can actually see the disks as they get moved around
[ December 27, 2002: Message edited by: Junilu Lacar ]

[James Chegwidden]

The TOH of program is very intuitive. You can find code for it in a lot of programming texts. The knapsack problem - look in a data structure text or on the internet.
Post some java code and we will help

[mike rivers]

thanks very much guys for all of your support. i still don't really know any real java, i am an absolute beginner, with a intermediate problem. i'm gonna go away now and see what i can do, and read around in these areas. i think i need to use arrays, and recursive queries, but i don't know how to do that, not that i'm asking you lot, although it would help ;-) but at least i have some idea where in the books i need to look.
thanks again, i thought the world of java was filled with rude people (sun's forums, they didn't help) until i was told about this place.

[David Weitzman]

Do you know what memoization is? The recursive solution to the knapsack problem is probably easier to understand than the iterative one, but it will have poorer performance unless you use memoization. I assume you can't include fractional items (correct me if I'm wrong).

[Ellen Zhao]

Mike,
I was searching information for my own here today, however I found this in a thread discussing threads

 public class Hanoi {
public static void main(String[] args) {
if (args.length != 4) {
System.out.println("usage: Hanoi #1 #2 #3 disks");
return;
}
if (args[3].equals(""))
return;
main(new String[] { args[0], args[2], args[1], args[3].substring(1)});
System.out.println("disk "+args[3].charAt(0)+" from "+args[0]+" to "+args[2]);
main(new String[] { args[1], args[0], args[2], args[3].substring(1)});
}
} 

Hope it could be helpful to you.
Ellen
ps: source of the code: https://coderanch.com/t/393005/java/java/return-statement-main

(Marilyn formatted code to not be all on one line)
[ December 28, 2002: Message edited by: Marilyn de Queiroz ]

[Barry Gaunt]

Was going to suggest that one myself.
And give it in like that on one long long line! Say that it's optimized.
Sorry Ellen,
-Barry

[mike rivers]

another step along the way, thanks guys! you're all so helpful. thanks!!
i'm using fractions so your suggestions will most certainly help - i'll see what the public library has.

[Anonymous]

Hey! That was my code, they've ripped away! ;-)
If you really want to take that Towers of Hanoi problem over the edge, have a look at this little (non-recursive!) monster:

public class Hanoi {
public static void main(String[] args) {
int n= 4; // four disks
for (int x=1; x < (1 << n); x++)
      System.out.println("from peg "+((x&x-1)%3)+
   " to peg "+(((x|x-1)+1)%3));
}
}

The piles are numbered 0, 1 and 2 respectively and the tower is moved from pile 0 to pile 1 if n is even, otherwise disks are moved from pile 0 to pile 2.
Enjoy,
Jos
[ December 29, 2002: Message edited by: Jos Horsmeier ]

[John Lee]

Originally posted by mike rivers:
the knapsack:
knapsack can hold 35kg
have 20 objects with random weights (1-5kg) and random value ($1-10)
object:given the knapsack can hold upto 20 objects. maximise the total value of the contents of the knapsack.

Common sense tells me:
you should pick the object with the most value/weight ratio, then pick the second most, ... , until you fill up the knapsack.
But you may reach number limit before you reach weight limit. In that case, you should:
1) keep going, until you reach weight limit, then, take some least expensive objects out to meet number limit;
2) then take out the existing least expensive object out, put in the outside most expensive object in, ... , repeat right before over weight limit.

[mike rivers]

just wanted to say a big thankyou to all who have posted here. any more suggestions are always appreciated.

[John Lee]

You are welcome!
In fact, I think knapsack is probablly more difficult than that. I will think more later.

[James Chegwidden]

Mike, what are using fractions on? You do not need to use them for Towers. As for the Knapsack I had to do it in school - in Pascal so it is not hard. This was years ago however.

[John Lee]

Fractions? you mean I can break object up and put art of it in? assuming value is distributed uniformly.
Well, that changes the solution a little bit.

[David Weitzman]

For the knapsack problem with fractional items allowed, the answer is the obvious one.
If one pound of gold dust is worth $20 and one pount of silver dust is worth $15, what would you fill your backpack with? I know what I would take . What if the backback can only hold a half pound worth of stuff? What if it can hold two pounds?
Without fractional items, the best solution involves constructing a table (2d array)

[John Lee]

Originally posted by David Weitzman:
[QB]If one pound of gold dust is worth $20 and one pount of silver dust is worth $15, what would you fill your backpack with? I know what I would take . What if the backback can only hold a half pound worth of stuff? What if it can hold two pounds?[QB]

Half-pound backpack: 1/2 pound gold, worth $10;
Two-pound backpack: 1 pound gold, 1 pound silver, worth $35;
Of course, the best way is always to take the credit card.

[Emile Ghazzawi]

Hi,
I am a friend of Mike Rivers and he has just contacted me and pointed me to this great site that you have got going here.
I am working with him on this project and as he stated earlier, we have pretty much been dropped in at the deep end without any prior knowledge of java.
I have been reading some of your replies and they are extremely interesting and helpful. Your help really is much appreciated guys.
As for the confussion regarding fractional items in the knapsack problem, only whole items may be used, although their values and weights are to an accuracy of 1 decimal place.
Any further help with these problems will be greatly appreciated and i already feel that your site will be a goldmine of information to me throughout the duration of my course.
Thanks guys and keep up the good work!
Regards,
Emile

[David Weitzman]

Originally posted by Emile Ghazzawi:

As for the confussion regarding fractional items in the knapsack problem, only whole items may be used, although their values and weights are to an accuracy of 1 decimal place.

Alrighty then. Note that since you have 20, just doing a brute force test of every possible selection of items would require 2^20 trials (each item is either in, or it isn't). That's just slightly over 1 million. The answer can be calculated using only primitives (just integer arithmatic), so if I look an some handy information in this article it turns out that 1 million trials should be pretty easy. I've just implemented a brute force solution and it seems to run in about a second.
Sooo... Brute force is probably the way to go on this problem. Is that enough to get you started?

[David Weitzman]

You might find this article useful also.

[John Lee]

Thanks!

[mike rivers]

it would appear that the brute force method is right for this exercise (and my level of programming). however, one of the questions asked by the lecturer is; what effect would increasing the number of variables have. i think that brute force could not realistically be used on a larger scale situation. - thank heavens we don't have to solve for a greater number of variables.

[David Weitzman]

You may not be familiar with asymptotic notation, but the brute force solution has a worst case (and best case) running time of O(2^n) where n is the number of items. There is a solution that uses a technique called dynamic programming that has a worst (and best) case running time of O(n*w) where w is the maximum weight that the knapsack can hold. The complexity of the brute force solution grows exponentially with the number of items, but the complexity of the dynamic programming solution grows at a linear rate.
It's not actually a good idea to do this (constant factors and non-constant but insignificant factors are being ignored), but let's plug in the numbers. For a brute force search, it takes 2^20 units of time (as I said above). The dynamic programming solution takes 20*35 units of time. 2^20 is a lot larger than 20*35.
It starts to be a problem when the only solution to a certain problem has exponential complexity (although if you proove that no such problem exists, you'll receive one million dollars--it's a long story).

[mike rivers]

thanks david, i think the concepts are becomming clearer. i'm going back to uni early on the 8th, so i can get to some books. i might well post some code around then.
$1 million! are you working on that one then? i take it its really hard.
thanks again

[David Weitzman]

Originally posted by mike rivers:
$1 million! are you working on that one then? i take it its really hard.

The problem is proving that P=NP or P!=NP, where P is the set of problems solvable in polynomial time or less and NP is the set of problems that can't be solved in polynomial times (or perhaps they can--that's the problem). If you want to go for the prize, check out this site;
[ January 02, 2003: Message edited by: David Weitzman ]

[mike rivers]

ohhh no! i left all that permutations, factorials, and combinations stuff behind me a few years ago. sounds like a shocker!
good luck with it.

[mike rivers]

ok so i made some code now for the knapsack. its not very complicated (but also not streamlined). i've created the 20 random objects, but i need to sort through array [b] now, find the highest value to weight ratio objects, place them in the sack, and subtract the object's corresponding weight value from the 35kg knapsack limit.
import java.awt.*;
import javax.swing.*;
public class knapsack extends JApplet{
public void paint (Graphics p){
float a[]=new float [40]; //initialises array "a"
a[0]=(int)(Math.random()*5+1);//generates the weight of the object
a[1]=(int)(Math.random()*10+1);//generates the value of the object

p.drawString("Weight in Kg of Object 1 = "+a[0] ,50,50);
p.drawString("Value in � of Object 1 = "+a[1] ,50,65);
float b[]= new float [20];
b[0]=(a[1]/a[0]);//creates the value of the object in pounds kilo
p.drawString("� per Kg of object 1 = "+b[0] ,50,80);
a[2]=(int)(Math.random()*5+1);
a[3]=(int)(Math.random()*10+1);
b[1]=(a[3]/a[2]);
p.drawString("Weight in Kg of Object 2 = "+a[2] ,50,100);
p.drawString("Value in � of Object 2 = "+a[3] ,50,115);
p.drawString("� per Kg of object 2 = "+b[1] ,50,130);//object 2

a[4]=(int)(Math.random()*5+1);
a[5]=(int)(Math.random()*10+1);
b[2]=(a[5]/a[4]);
p.drawString("Weight in Kg of Object 3 = "+a[4] ,50,150);
p.drawString("Value in � of Object 3 = "+a[5] ,50,165);
p.drawString("� per Kg of object 3 = "+b[2] ,50,180);//object 3
a[6]=(int)(Math.random()*5+1);
a[7]=(int)(Math.random()*10+1);
b[3]=(a[7]/a[6]);
p.drawString("Weight in Kg of Object 4 = "+a[6] ,50,200);
p.drawString("Value in � of Object 4 = "+a[7] ,50,215);
p.drawString("� per Kg of object 4 = "+b[3] ,50,230);//object 4

a[8]=(int)(Math.random()*5+1);
a[9]=(int)(Math.random()*10+1);
b[4]=(a[9]/a[8]);
p.drawString("Weight in Kg of Object 5 = "+a[8] ,50,250);
p.drawString("Value in � of Object 5 = "+a[9] ,50,265);
p.drawString("� per Kg of object 5 = "+b[4] ,50,280);//object 5

a[10]=(int)(Math.random()*5+1);
a[11]=(int)(Math.random()*10+1);
b[5]=(a[11]/a[10]);
p.drawString("Weight in Kg of Object 6 = "+a[10] ,50,300);
p.drawString("Value in � of Object 6 = "+a[11] ,50,315);
p.drawString("� per Kg of object 6 = "+b[5] ,50,330);//object 6

a[12]=(int)(Math.random()*5+1);
a[13]=(int)(Math.random()*10+1);
b[6]=(a[13]/a[12]);
p.drawString("Weight in Kg of Object 7 = "+a[12] ,50,350);
p.drawString("Value in � of Object 7 = "+a[13] ,50,365);
p.drawString("� per Kg of object 7 = "+b[6] ,50,380);//object 7
a[14]=(int)(Math.random()*5+1);
a[15]=(int)(Math.random()*10+1);
b[7]=(a[15]/a[14]);
p.drawString("Weight in Kg of Object 8 = "+a[14] ,50,400);
p.drawString("Value in � of Object 8 = "+a[15] ,50,415);
p.drawString("� per Kg of object 8 = "+b[7] ,50,430);//object 8

a[16]=(int)(Math.random()*5+1);
a[17]=(int)(Math.random()*10+1);
b[8]=(a[17]/a[16]);
p.drawString("Weight in Kg of Object 9 = "+a[16] ,50,450);
p.drawString("Value in � of Object 9 = "+a[17] ,50,465);
p.drawString("� per Kg of object 9 = "+b[8] ,50,480);//object 9

a[18]=(int)(Math.random()*5+1);
a[19]=(int)(Math.random()*10+1);
b[9]=(a[19]/a[18]);
p.drawString("Weight in Kg of Object 10 = "+a[18] ,50,500);
p.drawString("Value in � of Object 10 = "+a[19] ,50,515);
p.drawString("� per Kg of object 10 = "+b[9] ,50,530);//object 10
a[20]=(int)(Math.random()*5+1);
a[21]=(int)(Math.random()*10+1);
b[10]=(a[21]/a[20]);
p.drawString("Weight in Kg of Object 11 = "+a[20] ,350,50);
p.drawString("Value in � of Object 11 = "+a[21] ,350,65);
p.drawString("� per Kg of object 11 = "+b[10] ,350,80);//object 11
a[22]=(int)(Math.random()*5+1);
a[23]=(int)(Math.random()*10+1);
b[11]=(a[23]/a[22]);
p.drawString("Weight in Kg of Object 12 = "+a[22] ,350,100);
p.drawString("Value in � of Object 12 = "+a[23] ,350,115);
p.drawString("� per Kg of object 12 = "+b[11] ,350,130);//object 12
a[24]=(int)(Math.random()*5+1);
a[25]=(int)(Math.random()*10+1);
b[12]=(a[25]/a[24]);
p.drawString("Weight in Kg of Object 13 = "+a[24] ,350,150);
p.drawString("Value in � of Object 13 = "+a[25] ,350,165);
p.drawString("� per Kg of object 13 = "+b[12] ,350,180);//object 13

a[26]=(int)(Math.random()*5+1);
a[27]=(int)(Math.random()*10+1);
b[13]=(a[27]/a[26]);
p.drawString("Weight in Kg of Object 14 = "+a[26] ,350,200);
p.drawString("Value in � of Object 14 = "+a[27] ,350,215);
p.drawString("� per Kg of object 14 = "+b[13] ,350,230);//object 14

a[28]=(int)(Math.random()*5+1);
a[29]=(int)(Math.random()*10+1);
b[14]=(a[29]/a[28]);
p.drawString("Weight in Kg of Object 15 = "+a[28] ,350,250);
p.drawString("Value in � of Object 15 = "+a[29] ,350,265);
p.drawString("� per Kg of object 15 = "+b[14] ,350,280);//object 15

a[30]=(int)(Math.random()*5+1);
a[31]=(int)(Math.random()*10+1);
b[15]=(a[31]/a[30]);
p.drawString("Weight in Kg of Object 16 = "+a[30] ,350,300);
p.drawString("Value in � of Object 6 = "+a[31] ,350,315);
p.drawString("� per Kg of object 6 = "+b[15] ,350,330);//object 16
a[32]=(int)(Math.random()*5+1);
a[33]=(int)(Math.random()*10+1);
b[16]=(a[33]/a[32]);
p.drawString("Weight in Kg of Object 17 = "+a[32] ,350,350);
p.drawString("Value in � of Object 17 = "+a[33] ,350,365);
p.drawString("� per Kg of object 17 = "+b[16] ,350,380);//object 17

a[34]=(int)(Math.random()*5+1);
a[35]=(int)(Math.random()*10+1);
b[17]=(a[35]/a[34]);
p.drawString("Weight in Kg of Object 18 = "+a[34] ,350,400);
p.drawString("Value in � of Object 18 = "+a[35] ,350,415);
p.drawString("� per Kg of object 18 = "+b[17] ,350,430);//object 18

a[36]=(int)(Math.random()*5+1);
a[37]=(int)(Math.random()*10+1);
b[18]=(a[37]/a[36]);
p.drawString("Weight in Kg of Object 19 = "+a[36] ,350,450);
p.drawString("Value in � of Object 19 = "+a[37] ,350,465);
p.drawString("� per Kg of object 19 = "+b[18] ,350,480);//object19

a[38]=(int)(Math.random()*5+1);
a[39]=(int)(Math.random()*10+1);
b[19]=(a[39]/a[38]);
p.drawString("Weight in Kg of Object 20 = "+a[38] ,350,500);
p.drawString("Value in � of Object 20 = "+a[39] ,350,515);
p.drawString("� per Kg of object 20 = "+b[19] ,350,530); //object 20

}
}

[Greg Charles]

Originally posted by Junilu Lacar:
here are some tips for solving the tower of hanoi:
...

Some monks in Tibet have supposedly been playing this game for centuries (they have to move 64 disks) and when they are done, it will be the end of the world

On a tangent, why Tibet? Ha Noi is the capital of Viet Nam. For what it's worth, I described the Tower of Ha Noi puzzle to a number of people living in Ha Noi and they had never heard of it. BTW, to complete the puzzle of 64 disks, assuming you can move one disk per second without breaks or making any mistakes, would take something over 500 billion years. I think we'll find a faster way to end the world than those monks, whereever they are.

[David Weitzman]

Do you have any other programming experience? More specifically, are you familiar with loops? That whole method could be expressed with about ten or fifteen lines of code. By hardcoding the solution, you lose a lot of flexibility.
Also, you're using the fractional solution, but I thought you could only include whole items, right? If you can include fractional items, there remains an easier solution (and most of this post will be irrellevant). If not you can use brute force (which is not what you used). For the moment, let's leave Applets and GUI's behind. Just write a method with the following signature:

/**
 * 'weights' and 'values' are two arrays of length
 * N, where N is the number of items available
 * to choose from.  For each item K (where K
 * is in the range 0..N-1) the weight of
 * item K is stored in weights[K], and the value
 * is stored in values[K].
 *
 * This method will determine which subset of items
 * has a weight less than or equal to the
 * capacity and the greatest total value of
 * all subsets.  It returns the value of
 * that subset (it doesn't matter if multiple
 * valid subsets would yeild maximal value).
 *
 * Note: There may be
 * no item with a weight less than 'capacity'
 * (or the arrays may be of length 0), in which
 * case this method will return 0.
 *
 * Assumptions:
 *   weights.length == values.length == N
 *   capacity >= 0
 *   weights and values are non-negative
 *
 * (not all of these assumptions are necessary,
 *  but they don't hurt)
 */
public int getMaximumValue(int[] weights, int[] values, int capacity) {
 // code goes here
 return maximumValue;
}

If you want to use a recursive solution, you may want to create a helper function which you can call recursively, that might have a signature like this:

public int getMaximumValueHelper(int[] weights, int[] values, int numberOfItemsLookedAt,
        int valueOfItemsChosen, int capacityRemaining) {
 // code goes here
 return maximumValue;
}

Calling getMaximumValue(weights, values, capacity) is the same as calling getMaximumValueHelper(weights, values, 0, 0, capacity).
I originally used an iterative solution using the bitfield counter method described in the link I posted above, but if you aren't somewhat familiar with how binary numbers are manipulated in programming languages then you probably wouldn't understand it (that version imposes a maximum of 32 items). The recursive solution should be universally understandable.
The check that your method works, you can write a main() method with tests something like this:

public static void main(String[] args) {
  int[] weightsA = { 21, 20, 15};
  int[] valuesA  = {100, 51, 50};
  int[] capacityA = 35;
  int[] expectedResultA = 101;
  int resultA = getMaximumValue(weightsA, valuesA, capacityA);
  if (resultA == expectedResultA) {
    System.out.println("Test A Passed. Result = " + resultA);
  } else {
    System.out.println("Test A Failed. Expected " + expectedResultA + " but received " + resultA);
  }
}

This is only one test (there should be more) the makes sure you don't use the fractional knapsack problem solution. The item with the highest value to weight ratio is clearly the first one, packing 100 value in only 21 weight. If you chose that item however, you wouldn't be able to fit anything else in the bag. On the other hand, you can fit both of the other items, which would give you a higher value.
The trick with the 0-1 (non-fractional) knapsack problem is that sometimes you can fit two items with a lower value to weight ratio instead of just one item with a high value to weight ratio. On the fractional knapsack problem, you would have just chopped the most efficient item in half and took whatever you could fit. Is this more clear?
[ January 09, 2003: Message edited by: David Weitzman ]

[Emile Ghazzawi]

Hi, buddy of Mike here again!
Thanks for the great advice David, it came in very handy. I have some previous experience of programming in both Pascal and Visual Basic therefore i am fairly aquainted with loops and other conditional statements. I took your suggestion into account and managed to condense Mikes code into the code below, it all seems to work ok.
The main problem now is trying to sort them and select the best objects. Would using Switch Conditionals be the right way to go about it? Also it seems that i may need to use a multi dimensional array so that all of the variables can be sorted at the same time, otherwise if one array is sorted and not the others, the various values will no longer bear any significance as they will be attached to another object. Your advice will once again be greatly appreciated. Please also feel free to make reference to VB or Pascal as this may help. Any code modifications or additions may also aid in my learning.
Code:
import java.awt.*;
import javax.swing.*;
public class knapsack extends JApplet{

public void paint (Graphics g){
float[] weight=new float[21];
float[] value=new float[21];
float[] ratio=new float[21];
int i;
for (i=0;i<=20;i++){
weight[i]=(float)(Math.random()*5+1);
value[i]=(float)(Math.random()*10+1);
ratio[i]=(value[i]/weight[i]);
}
}
}
Thanks a lot guys for all of the help you are giving!
You guys are great!
Regards,
Emile

[Emile Ghazzawi]

Hi again guys,
Thanks to all your great help and advice i have finally created a working knapsack program, although i still have a small dilemma with the Towers of Hanoi problem that i need some help with. Although the knapsack program is completed i have posted the code so that you can hopefully provide me with some feedback or suggestions on my first attempt at java.

  
import java.awt.*;
import javax.swing.*;
public class knapsack extends JApplet{

public void paint (Graphics g){
float[] weight=new float[20];
float[] value=new float[20];
float[] ratio=new float[20];
float[] finalvalue=new float[20];
boolean[] selected=new boolean[20];
int i;
float currentweight=0f;
float testweight=0f;
float totalvalue=0f;
for (i=0;i<=19;i++){
weight[i]=(float)(Math.random()*5+1);
value[i]=(float)(Math.random()*10+1);
ratio[i]=(value[i]/weight[i]);
}

for (i=0;i<=19;i++){
if (ratio[i] >9 && currentweight <=35){ 
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >8 && ratio[i] <=9 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >7 && ratio[i] <=8 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >6 && ratio[i] <=7 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >5 && ratio[i] <=6 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >4 && ratio[i] <=5 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >3 && ratio[i] <=4 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >2 && ratio[i] <=3 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >1 && ratio[i] <=2 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}
for (i=0;i<=19;i++){
if (ratio[i] >0 && ratio[i] <=1 && currentweight <=35) {
testweight=currentweight;
testweight+=weight[i];
if (testweight <=35){
finalvalue[i]=value[i];
currentweight+=weight[i];
selected[i]=true;
}
}
}

for (i=0;i<=19;i++){
totalvalue+=finalvalue[i];
}
g.drawString("Total Value �"+totalvalue ,280,500);
g.drawString("Total Weight "+currentweight+" Kg" ,280,520);
g.drawString("Object No." ,50,50);
g.drawString("Value", 200,50);
g.drawString("Weight", 350,50);
g.drawString("Selected", 500,50);

for (i=0;i<=19;i++){
g.drawString(""+i,80,70+i*20);
g.drawString("�"+value[i],200,70+i*20);
g.drawString(""+weight[i]+" Kg",350,70+i*20);
g.drawString(""+selected[i],510,70+i*20);
}
}
}

Ok, now to my dilemma! I have created a Towers of Hanoi program bu t i cannot work out how to create it so that it works in a browser. I have posted my code below which is designed to be run from the command line, any help on how to convert it to run in a browser would be greatly appreciated. I have tried everything (well whats in my limited arsenal anyway :-)) to get it to work in a browser.

import java.awt.*;
import javax.swing.*;
public class hanoi extends JApplet{
    public static void main (String[] args){        
        int height = 3;
        System.out.println("Height of Tower = "+ height) ;
        movetowers(height, 1, 2);
    }
    
    static void movetowers(int h, int a, int b){
        if (h>0){
            movetowers (h-1, a, 6-a-b);
            System.out.print("Move Disk "+ h);
            System.out.println(" from Pin "+ a + " to Pin " + b);
            movetowers (h-1, 6-a-b, b);
        }
    }
}

I eagerly await a reply and hopefully some feedback. I also look forward to your comments regarding my first program.
This Java stuff has started to rub off onto me and i am actually starting to find myself enjoying it. I have already ordered a bunch of books from amazon!
Thanks once again guys!
P.S. I would like to give credit to Junilu Lacar who suggested a method for working out the "Using" peg in the Towers of Hanoi problem, which i have incorporated into my program. Also, all you others that have helped me along the way, THANKS!.
[ January 15, 2003: Message edited by: Emile Ghazzawi ]

[David Weitzman]

Emile, here's a useful algorithm which will allow you to determine the greatest ratio with much less work.

public int getPositionOfMax(float[] ratio) {
  int positionOfMax = -1;
  float valueOfMax = Float.MAX_VALUE;
 
  for (int i = 0; i < ratio.length; i++) {
    if (ratio[i] < valueOfMax) {
      positionOfMax = i;
      valueOfMax = ratio[i];
    }
  }
 
  return positionOfMax;
}

If there are no items left in the list, getPositionOfMax() returns -1. Otherwise it will return the index of the greatest element.
Suppose you found something with a high value to weight ratio at position K using getPositionOfMax(ratio) and you still have room left in the pack. To find the next most valueble item, just set ratio[K] to 0 and call getPositionOfMax(ratio) again.
If you are solving the fractional knapsack problem (once again I'm unclear on this point) then you cannot just use a boolean array 'selected' -- you need a float[] array 'amountSelected'. The last item chosen may not fully fit. For all but possibly the last item, amountSelected[i] will equal value[i], but it's important to be clear because a wrong solution might not fully use the most useful items. Even if you know what your solution does, it's important to be explicit so that someone viewing the result doesn't wonder why you put 22 kg worth of junk in a 20 kg bag. If you are solving the 0-1 knapsack problem then your solution just plain won't work.
I still recommend that you avoid using applets unless it's a requirement for the assignment. If you must, here is the most significant problem I notice:
Be aware the the paint() method can be called again at any time (for example, if another window blocks the applet and then gets moved out of the way). Since you're generating new random values on every call to paint(), the set of items could unexpectly change at any time while someone is viewing the applet! It's probably best to put the calculations in a method with the signature "public void init()" and then just display the results in paint().

[Emile Ghazzawi]

Hello again,
Thanks for the advice with the algorithm, it will definately come in handy! As for the use of the applet, i am afraid that part of this assignment is that the programs must run in a browser, namely Internet Explorer.
Any advice or example code on how i could change my Towers of Hanoi program so that its runs in a browser would be greatly appreciated. What you posted about getting it to work in a browser makes sense but it still doesnt make the process of changing the code any clearer.
You guys have been a great help and i am sure that you will be an invaluable source for time to come as i embark on my quest to learn Java :-)!
Thanks once again and i eagerly await your reply.
Emile

[David Weitzman]

public class MyApplet extends JApplet {
  float[20] weight;
  float[20] value;
  float[20] ratio;
  float[20] amountUsed;
 
  public void init() {
    // generate random items
    ...
    value[i] = /* Random Number */;
    ratio[i] = value[i]/weight[i];
    ...
 
    // select best items
  }
 
  public void paint(Graphics g) {
    for (int i = 0; i < 20; i++) {
      // write item weight, value, ratio, and amount used
    }
  }
}

I don't do much GUI work, but for Hanoi you might try something like this:

public class Hanoi extends JApplet {
  java.awt.TextArea _ta;
 
  public void init() {
    _ta = new java.awt.TextArea(row, columns);
    _ta.setEditable(false);
    add(_ta);
    doHanoiStuff();
  }
 
  public void doHanoiStuff() {
    // blah blah blah
    // instead of System.out.println():
    _ta.append("Move this to that\n");
    // blah blah blah
  }
}

[ January 15, 2003: Message edited by: David Weitzman ]

[mike rivers]

just a final note to say thankyou to everyone (especially david, you ra star)who posted here. we finally made it, with seconds to spare.