PHP algorithms: knapsack 0/1

The problem of optimization.

Knapsack algorithm is frequent used piece of code appearing in variety different applications in various forms. Given a container with limited capacity and a set of items represented in two dimensions (weight/value), the goal is to find most valuable combination of items. To achieve this we must sort items by weight/value ratio in ascending order first.

Building values matrix.

Now we are ready to build an array containing all item values for each weight.

For better understanding how algorithm is going to work, table below shows every value for our loop. Numbers in red, are values of finally selected items.

weight value 0 1 2 3 4 5 6 7 8
5 6 0 0 0 0 0 1 1 1 1
3 5 0 0 0 5 5 5 5 5 6
3 6 0 0 0 6 6 6 6 6 7
1 2 0 2 2 8 8 8 8 8 8

Viewing selected items.

Unfortunately viewing results is not trivial. In order to display selected items we must walk backwards selected values and find corresponding items.

 

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditEmail this to someoneShare on StumbleUpon