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: five_belliez@hotmail.com

- 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 ]

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

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.

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

Hope it could be helpful to you.

Ellen

ps: source of the code: http://www.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 ]

And give it in like that on one long long line! Say that it's optimized.

Sorry Ellen,

-Barry

Ask a Meaningful Question and HowToAskQuestionsOnJavaRanch

Getting someone to think and try something out is much more useful than just telling them the answer.

If you really want to take that Towers of Hanoi problem over the edge, have a look at this little (non-recursive!) monster:

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 ]

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.

Ranch Hand

Author and Instructor, my book

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)

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 wouldyoufill 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.

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

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?

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).

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 ]

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

}

}

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.

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:

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:

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:

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 ]

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

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.

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.

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 ]

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().

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