# Knapsack Problem In Analysis And Design Of Algorithms

## Introduction

A thief robbing a store that can carry a maximal weight of 'w' into his knapsack. There are 'n' no of items in store available and ith items weight are Wand the  worth of thease items are Pi dollars. What items should the thief take and how?

So let’s see how to solve this thief problem.

## What is the Knapsack Problem?

A thief went to a store to steal some items. There are multiple items available of different weights & profits.

Let suppose there are ‘n’ No. of items & weight of these are W1, W2,………Wn respectively, and the profit of these items are P1, P2,……….Pn respectively.

The thief wants to do steal in such a way so that his overall profit be ‘Maximum ’ and ‘Capacity constraint’ of knapsack don’t break.

Knapsack Problem may be of 2 types:
• [A] 0/1 Knapsack problem
• [B] Fractional Knapsack problem

## 0/1 Knapsack problem

In this problem, either a whole item is selected(1) or the whole item not to be selected(0).

Here, the thief can’t carry a fraction of the item.

In the LPP(Linear programming problem) form, it can be described as:

Formula

## Fractional Knapsack problem

In this problem, a whole item can be selected (1) or a whole item can’t be selected (0) or a fraction of item can also be selected (between 0 or 1)

In the LPP(Linear programming problem) form, it can be described as:

So this Knapsack problem can be solved by using these following methods:
1. Greedy method
2. Dynamic Programming method
3. Back Tracking method
4. Branch & Bound

## Greedy Method

A greedy algorithm is an algorithm that follows the problem solving met heuristic of making the locally optimal choice each stage with the hope of finding the global optimum.

The greedy method is a powerful technique used in the design of algorithms. Almost all problems that come under this category have 'n' inputs. A subset of the given set of inputs that satisfies some given constraints is to be obtained. Such a subset is called a feasible solution. Now the problem is to find a feasible solution that maximizes or maximizes a given objective function. Such a function is called an Optimal solution. The Greedy method works in stages.
• Feasible- It should satisfy the problem's constraints
• Locally Optimal- Among all feasible solutions the best choice is to be made.
• Irrevocable-Once the particular choice is made then it should not get changed on subsequent steps.
The greedy method can be characterized as being 'Short-sighted', and 'non-recoverable'. They are ideal only for problems that have optimal substructure. One way to construct a solution for such optimization problems is the greedy method . in which we construct the solution in stages. At each stage, we make a decision that appears to be the best according to certain greedy criteria, and will not be changed in later stages. Hence, each decision should assume the feasibility. Although the greedy method doesn't lead to an optimal solution. eg. in the traveling salesman problem, it does in some other cases.

## Dynamic Programming Method

Dynamic programming is a problem-solving technique that, like divide and conquer, solves problems by dividing them into sub-problems. Dynamic programming is used when the sub-problems are not independent. eg. when they share the same sub-problems.
• Is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure. When applicable, the method takes much less time than naive methods.
• Is a technique for computing recurrence relations efficiently by sorting partial results. It is typically applied to optimization problems. In such problems, there can be many possible solutions. Each solution has a value, and wish to find a solution with the optimal value. Such a solution is called an optimal solution to the problem, since there may be several solutions that achieve the optimal value.
• Principle of Optimality: To use dynamic programming, the problem must observe the principle of optimality, that whatever the initial state is, remaining decisions must be optimal with regard to the state following from the first decision must be optimal with regard to the state following from the first decision. Combinatorial problems may have this property but may use too much memory/time to be efficient.

## Approaches in Dynamic Programming

There are two approaches to solving a dynamic programming problem.

Bottom-up Approach

The bottom-up approach simply means storing the results of certain calculations, which are then re-used later because the same calculations is a sub-problem in a larger calculation.

Top-down Approach

The top-down approach involves formulating a complex calculation as a recursive series of simpler calculations.

Backtracking Method

Backtracking can be described as an organized exhaustive which offers avoids searching for all possibilities. The technique is generally suitable for solving problems where a potentially large but finite number of solutions have to inspected.

Backtracking can be applied only for problems that admit the concept of a partial candidate solution and a relatively quick test of whether it can possibly be completed to a valid solution.

Backtracking is an important tool for solving constraint satisfaction problems, such as crossword, verbal arithmetic, and many other puzzles. It is often the most convenient (If not them most efficient) technique for parsing for the knapsack problem and other combinational optimization problems. It is so the basis of the so-called logic programming languages such as Icon, Planner a Prolog.

## Backtracking Problems

In backtracking, the problem can be categorized into three categories.

Decision Problem

In the decision problem we find “whether there are any feasible solutions?”

Optimization Problem

In optimization problems, we find “whether there exist any best solutions?”

Enumeration Problem

In the enumerations problem, we find all the possible feasible solutions.

Branch and Bound Method-Branch and bound is a state-space search method in which all the children of a node are generated before expending any of its children.

## Branch and Bound Terminology

Live Node

A node that has been generated and all of whose children have not yet been generated is called a live node. The live node whose children are currently being generated is called the E-node.

E-node

A live node whose children are currently being explored. In other words, an E-node is a node currently being expended.