Knapsack Example (Bruteforce)
Author: Shmulik London
0-1 Knapsack problem with real weights
The problem: A thief robbing a store finds n items; the
ith item is worth vI dollars
and weights wI pounds, where vI
and wI are real numbers, but he
can carry at most W pounds in his knapsack for some real W.
What items should he take?
Formulation from 'Introduction to Algorithms / Cormen, Leiserson
& Rivest'.
Snapshot of KnapsackDemoApplet running
About the demonstrating Applet
The snapshot above is on an Applet demonstrating a naive solution of the
problem with popcorn. There are 40 items shown as colored bricks; the length
of a brick represents the weight of the item, an the label on the brick
is the worth of the item in dollars. In the bottom of the Applet window,
there is a blue frame that represents the knapsack; the lengh of the frame
is the total weight W. The problem is pick up from the collection
of bricks at the top of the window, a set of bricks which will fit into
the frame, and whose worth will sum up to the maximum possible value.
Implementation
The implementation here simply sends enumerous ComputationPackets, each
one returns the best solution out of randomly choosen 10000 possible solutions.
On the return of each ComputationPacket the Applet updates the best solution
achived so far. The number of packet that was send, number of packets arrived
and the maximum worth achived, are displayed in the status line.
Source
You can look at KnapSackDemoApplet.java
for the source code. The code as it is sends the Computelets to be executed
on the local machine. Check the 'Java Popcorn Tutorial' to change it to
use the Popcorn Market.