The Knapsack Problem
Written by Mike James   
Thursday, 28 June 2018
Article Index
The Knapsack Problem
Knapsack solved
Speed

 

Speed And Heuristics

If you try this program out you will find that at first everything works quickly with answers flashing up after a few seconds. However if you try N=30,000 say then things slow to a stop.

The problem is that the knapsack algorithm slows down as 2^N which makes the problem for 30,000 number about 10^10000 (yes 1 followed by 10,000 zeros) times longer to solve than the 1000 number problem – so don't wait for a solution too long. 

To see this in action try N=50, 500 and 5000. In most cases you will give up waiting for the 5000 case. 

It is the huge number of different combinations that have to be considered that makes the task so difficult.

It is a the definition of NP problems that finding a solution takes a long time but verifying that you have a solution is very quick. In this case you have to search all possible combinations to find a solution but checking that you have a solution is just a matter of adding the values provided up and checking that the sum to the target and are in the array. 

 

However, how do you know that there isn't a short cut that means you don't have to consider every possible combination?

There are algorithms that attempt to solve the problem more quickly. For example there are variations on the greedy algorithm - pick the first number closest to the target, then the next closest and so on. A more sophisticated greedy algorithm is based on dynamic programming. The key factor in all of these algorithms is that they usually find the solution in reasonable time but there is no promise that they will ever find the solution without examining every possible combination. They may be advanced but they are still "heuristics", i.e. algorithms that usually work quicker than an exhaustive search but this isn't guaranteed.

 

knapsack

Uses

The knapsack problem is the basis for one method of public key cryptography.

A set of numbers in a given order is made public and any user can code a message by multiplying each number by a zero or a one according to the messages binary representation.

All of the values are added up to give a single value and this is of course the "target" value in a knapsack problem using the given set of numbers.

Of course you can't decode the message because this would mean solving the knapsack problem for very very large N. However the intended recipient of the message can decode it because they have a "shadow" set of numbers with a special properties that make the solution of the knapsack problem very easy. So anyone can code a message using the public numbers but only the recipient can decode it without solving the full knapsack problem.

Unfortunately a few years ago it was discovered that the need to use a "shadow" set of values made the knapsack problem posed by the public values rather easier to solve than was originally thought – i.e. there was a way of doing the job much faster than 2^N. So now the knapsack code is no longer used but it is still interesting and with a better set of shadow values might even be resurrected one day.

 

 

The program can be downloaded from the CodeBin. Note you have to register with I Programmer to access this.  

Related Articles:

How not to shuffle - the Knuth Fisher-Yates algorithm       

Recursion

Public Key Encryption

 


Setting Up Site-To-Site OpenVPN

Setting up a point-to-point VPN is relatively easy but site-to-site is much more complicated involving certificates and more IP addresses than you can count. Find out how to do it using OpenVPN.



QuickSort Exposed

QuickSort was published in July 1961 and so is celebrating its 60th birthday.  QuickSort is the most elegant of algorithms and every programmer should study it. It is also subtle and this often m [ ... ]


Other Projects


Crazy Clocks
10/03/2024

It's that time again when the clocks change and  time is of the essence and I indulge my interest in crazy clocks. I am always surprised that there are still new ideas for how to display the time [ ... ]



Bun Shell Released
29/02/2024

The developers of the Bun JavaScript runtime have released Bun Shell, a new experimental embedded language and interpreter in Bun that lets you run cross-platform shell scripts in JavaScript and TypeS [ ... ]


More News

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

 

<ASIN:9810221207>

<ASIN:059651610X>

<ASIN:3540613560>



Last Updated ( Thursday, 28 June 2018 )