Knapsack Algorithm | Greedy Method in Knapsack Algorithm

What is an Algorithm?

Although there is no universally agreed on wording to describe this notion, there is a general agreement about what the concept means:

An algorithm is a sequence of an unambiguous instructions for solving a problem ie., obtaining a required output for any legitimate input in a finite amount of time.

 

This definition can be illustrated by simple diagram shown below:

Figure: The notion of an algorithm

As illustrating the notion of the algorithm, we consider three methods for solving the same problem computing the common devisors of two integers.

1. As illustrating the notion of an algorithm we consider three methods for solving the same problem.
2. The  non ambiguity requirement for each step of an algorithm cannot be compromised.
3. The range of inputs for which an algorithm works has to be specified carefully.
4. The same algorithm can be represented in several different ways there may exist several algorithms for solving the same problem.

Algorithms for the same problem can be based on very different ideas and can solve the problem with dramatically different speeds.

Recall that the greatest common divisor of two nonnegative, not-both-zero integers m and n, denoted gcd(m, n), is defined as the largest integer that divides both m and n evenly, i.e., with a remainder of zero.

In modern terms, Euclid’s algorithm is based on applying repeatedly the equality;

gcd(m, n) = gcd(n, m mod n),

where m mod n is the remainder of the division of m by n, until m mod n is equal to 0.

Knapsack problem:

Given n items of known weights, w1, w2, …., wn and values v1, v2, …., vn and knapsack of capacity W,  find the most valuable subset of the items that fit into the knapsack.

If you do not like the idea of putting yourself in the shoes of a thief who wants to steal the most valuable loot that fits into his knapsack, think about the transport plane that has to deliver the most valuable set of items to a remote location without exceeding the plane’s capacity.

Figure: Solution to a small instance of the knapsack problem by exhaustive

search.

The exhaustive search approach to this problem leads to generating all the subsets of the set of n items given, computing the total weight of each subset in order to identify feasible subsets (ie., The ones with the total weight not exceeding the knapsack capacity),  and finding the largest subset value among them.

The number of subjects of an element set is 2n, the exhaustive search leads to a Ω(2n) algorithm, no matter how efficiently individual subsets are generated.

Figure: (a) Instance of the knapsack problem. (b) Its solution by exhaustive search.

The information about the optimal selection is in bold.

Thus, the knapsack problems considered above, exhaustive search leads to algorithms that are extremely inefficient on every input. In fact, these two problems are the best-known examples of so called NP-hard problems.

No polynomial-time algorithm is known for any NP hard problem. Moreover, most computer scientists believe that such algorithms do not exist, although this very important conjecture has never been proven.