ScalaFX didactic application for the Knapsack problem

Branch & Bound solution


KnapScal is a didactic ScalaFX application dedicated to the Knapsack problem.

It can solve an instance of the problem by employing different techniques:

As shown in the screenshots below, the latest version of the application employs the EighthBridge library to actually render the Knapsack tree in a Branch & Bound solution!


KnapScal requires Java 8 Update 91 or later compatible version.

Running KnapScal

The suggested way to run KnapScal is MoonDeploy, as it will automatically download and launch the application - just click the Run with MoonDeploy button.

Otherwise, to start the application: 1. Download and decompress the binary zip archive 2. Run the file bin/KnapScal (on UNIX) or bin/KnapScal.bat (on Windows)

Branch & Bound solution

KnapScal now renders the Branch & Bound solution as a tree, just as expected.

Zooming and panning

Laying out the nodes

Starting from version 3, KnapScal automatically lays out the tree nodes; however, should you notice overlapping nodes, you can drag and drop the nodes in the tree itself, to reposition them

Employing the kernel

KnapScal-core, the underlying library, can be used in other applications for the JVM.


Problem window

Branch & Bound solution

Dynamic programming solution

Optimized dynamic programming solution

Special thanks

Special thanks to Professor Silvano Martello for his valuable advice and suggestions.

Further references