# BACKPACKER ALGORITHAM

### BACKPACKER ALGORITHAM (KNAPSACKER):-

Backpack problem: is a one of the classical optimization problem.

Given a set of items, each item with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible.

Definition: Given items of different values and volumes, to find the most valuable set of items that fits in a Backpack of fixed volume.

### 0-1 knapsack problem

Fractional knapsack problem: to solving fractional knapsack problem we are using greedy algorithm.

We're usually dealing with a knapsack problem when you're give the cost and the benefits of certain objects and asked to obtain the maximum benefit so that the sum of the costs is smaller than a given value. We've got the fractional knapsack problem when we can take fractions (as opposed to all or nothing) of the objects.

Definition: Number of each item can be a fractional. it presents optimal substructure property.

### Example for fractional knapsack problem:

Knapsack capacity C = 5

Sort items by decreasing value-per-kilogram(kg) D

\$200

B

\$300

A C

\$160

\$150

1kg 3kg 2kg 5kg

Value/kg: 150 100 80 40

If the knapsack holds 5kg , so the answer is : A = 1kg

B = 3kg

C = 1kg total value = \$ 530.

The idea is to calculate for each object the ratio of value/cost, and sort them according to this ratio. Then you take the objects with the highest ratios and add them until you can't add the next object as whole. Finally add as much as you can of the next object.

### Greedy-fractional-knapsack Algorithm (w, p, C):

FOR i =1 to n
do x[i] =0
weight = 0
while weight < C
do i = best remaining item
IF weight + w[i] ≤ C
then x[i] = 1
weight = weight + w[i]
else
x[i] = (w - weight) / w[i]
weight = C
return x

Note: The Greedt solution is always optimal for the fractional knapsack problem but not same for the 0-1 knapsack problem.

0-1 knapsack problem : I am using Dynamic programming method to solve our 0-1 knapsack problem.

Defination: Number of each item is either 0 or 1. it presents optimal substructure property .

### Dynamic programming :

Definition: Solve an optimization problem by caching sub problem solutions rather than re computing them.

It's used for optimization problems, the basic idea is to break down the problem into recurring subproblems (small problems), and here is the simple way to combine optimal solution of subproblems to get an optimal solution of main problem.

Dynamic programming often produces a polynomial algorithm for finding the optimal solution and more efficient than “brute-force methods” which is solve the same subproblems over and over again. The simple concepts of Dynamic programming is Optimal substructure, Overlapping subproblems and designing a table of solved subproblems that are used to solve larger ones.

### Let's run our algorithm on the following data:

N = 5 (objects or items)

C = 5 (Max weight)

Items (weight,profit) : (1,6) (1,11) (3,17) (2,3) (2,9)

For w = 0 to C

B[0,w] = 0

And

For n = 1 to N

B[I,0] = 0

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 1, pi= 6, wi = 1, w = 1,….5, w - wi = 0

if wi <= w //object n can be part of the solution

if pi + B[i-1,w- wi] > B[i-1,w]

B[i,w] = pi + B[i-1,w- wi]

else B[i,w] = B[i-1,w] // wi > w

like above, apply for all cells in 1st row

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 2, pi= 11, wi = 1, w = 1, w - wi = 0

if wi <= w //object n can be part of the solution

if pi + B[i-1,w- wi] > B[i-1,w]

B[i,w] = pi + B[i-1,w- wi]

else B[i,w] = B[i-1,w] // wi > w

like above, apply for all cells in 2nd row

This is the algorithm finds the maximum possible values only that can carried in the knapsack.

### To find the actual knapsack items, we can Extracting the solution:

B[N,C] is the maximal value of items that can be placed in the Backpack

Let i = n and k = C

If B[i,k] ≠ B[i-1,k] then mark the nth item in the Backpack

i = i - 1, k = k - wi

else

i = i - 1 Assume the ith item is not in the Backpack

So start with B(5,5) which means use all objects 1-5 to get a solution with weight = 5

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 5, k = 5, pi= 9, wi = 2, B(i,k) = 34, B(i-1,k) = 34

If B[i,k] ≠ B[i-1,k] then mark the nth item in the Backpack

i = i - 1, k = k - wi

else

i = i - 1 Assume the ith item is not in the Backpack

B(5,5) = B(4,5) and B[(4, 5-2) + 9] != 34

So don't include object 5

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 4, k = 5, pi= 3, wi = 2, B(i,k) = 34, B(i-1,k) = 34

If B[i,k] ≠ B[i-1,k] then mark the nth item in the Backpack

i = i - 1, k = k - wi

else

i = i - 1 Assume the ith item is not in the Backpack

B(4,5) = B(3,5) and B[(3, 5-2) + 17] = 34

So don't include object 4

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 3, k = 5, pi= 17, wi = 3, B(i,k) = 34, B(i-1,k) = 17

If B[i,k] ≠ B[i-1,k] then mark the nth item in the Backpack

i = i - 1, k = k - wi

else

i = i - 1 Assume the ith item is not in the Backpack.

B(3,5) != B(2,5) and B[(2, 5-3) + 17] = 34

So include object 3

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 2, k = 2, pi= 11, wi = 1, B(i,k) = 17, B(i-1,k) = 6

If B[i,k] ≠ B[i-1,k] then mark the nth item in the Backpack

i = i - 1, k = k - wi

else

i = i - 1 Assume the ith item is not in the Backpack.

B(2,5) != B(1,5) and B[(1, 2-1) + 11] = 17

So include object 2

Items : 1 = (1,6), 2 = (1,11), 3 = (3,17), 4 = (2,3), 5 = (2,9)

i = 1, k = 1, pi= 6, wi = 1, B(i,k) = 6, B(i-1,k) = 0

If B[i,k] ≠ B[i-1,k] then mark the nth item in the Backpack

i = i - 1, k = k - wi

else

i = i - 1 Assume the ith item is not in the Backpack.

B(2,5) != B(1,5) and B[(1, 1-1) + 6] = 6

So include object 1

Final answer: The optimal knapsack contains {1,2,3}

Note: the optimal solution for 0-1 knapsack cannot contain same as in the greedy solution.

Dynamic 0-1 knapsack algorithm : (p, w, n, C)

FOR w = 0 TO C
DO B[0, w] = 0
FOR i=1 to n
DO B[i, 0] = 0
FOR w=1 TO C
DO IFf wi ≤ w
THEN IF pi + B[i-1, w-wi]
THEN B[i, w] = pi + B[i-1, w-wi]
ELSE B[i, w] = B[i-1, w]
ELSE
B[i, w] = B[i-1, w]

### Conclusion:

The fractional knapsack problems can be solved with greedy algorithm

The 0-1 knapsack problems can be solved with Dynamic programming

Dynamic programming method is use full for some specific kind of problems

Word doc goes here, ignore any pictures that are in them