Algorithm

Getting Started with AlgorithmWhat is an Algorithm?

Characteristics of Algorithm1 Topic

Analysis Framework

Performance Analysis3 Topics

Mathematical Analysis2 Topics

Sorting AlgorithmSorting Algorithm10 Topics

Searching Algorithm6 Topics

Fundamental of Data StructuresStacks

Queues

Graphs

Trees

Sets

Dictionaries

Divide and ConquerGeneral Method

Binary Search

Recurrence Equation for Divide and Conquer

Finding the Maximum and Minimum

Merge Sort

Quick Sort

Stassen’s Matrix Multiplication

Advantages and Disadvantages of Divide and Conquer

Decrease and ConquerInsertion Sort

Topological Sort

Greedy MethodGeneral Method

Coin Change Problem

Knapsack Problem

Job Sequencing with Deadlines

Minimum Cost Spanning Trees2 Topics

Single Source Shortest Paths1 Topic

Optimal Tree Problem1 Topic

Transform and Conquer Approach1 Topic

Dynamic ProgrammingGeneral Method with Examples

Multistage Graphs

Transitive Closure1 Topic

All Pairs Shortest Paths6 Topics

BacktrackingGeneral Method

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Participants2253
Knapsack Problem
Knapsack Problem:
Knapsack is basically means bag. A bag of given capacity.
We want to pack n items in your luggage.
 The ith item is worth v_{i} dollars and weight w_{i} pounds.
 Take as valuable a load as possible, but cannot exceed W pounds.
 v_{i} w_{i} W are integers.
 W ≤ capacity
 Value ← Max
Input:
 Knapsack of capacity
 List (Array) of weight and their corresponding value.
Output: To maximize profit and minimize weight in capacity.
The knapsack problem where we have to pack the knapsack with maximum value in such a manner that the total weight of the items should not be greater than the capacity of the knapsack.
Knapsack problem can be further divided into two parts:
1. Fractional Knapsack: Fractional knapsack problem can be solved by Greedy Strategy where as 0 /1 problem is not.
It cannot be solved by Dynamic Programming Approach.
0/1 Knapsack Problem:
In this item cannot be broken which means thief should take the item as a whole or should leave it. That’s why it is called 0/1 knapsack Problem.
 Each item is taken or not taken.
 Cannot take a fractional amount of an item taken or take an item more than once.
 It cannot be solved by the Greedy Approach because it is enable to fill the knapsack to capacity.
 Greedy Approach doesn’t ensure an Optimal Solution.
Example of 0/1 Knapsack Problem:
Example: The maximum weight the knapsack can hold is W is 11. There are five items to choose from. Their weights and values are presented in the following table:
The [i, j] entry here will be V [i, j], the best value obtainable using the first “i” rows of items if the maximum capacity were j. We begin by initialization and first row.
V [i, j] = max {V [i  1, j], v_{i} + V [i  1, j w_{i}]
The value of V [3, 7] was computed as follows:
V [3, 7] = max {V [3  1, 7], v_{3} + V [3  1, 7  w_{3}] = max {V [2, 7], 18 + V [2, 7  5]} = max {7, 18 + 6} = 24
Finally, the output is:
The maximum value of items in the knapsack is 40, the bottomright entry). The dynamic programming approach can now be coded as the following algorithm:
Algorithm of Knapsack Problem
KNAPSACK (n, W)
1. for w = 0, W
2. do V [0,w] ← 0
3. for i=0, n
4. do V [i, 0] ← 0
5. for w = 0, W
6. do if (w_{i}≤ w & v_{i} + V [i1, w  w_{i}]> V [i 1,W])
7. then V [i, W] ←
v_{i} + V [i  1, w  w_{i}]
8. else V [i, W] ← V [i  1, w]