Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 35, Topic 3
In Progress

Knapsack Problem

Lesson Progress
0% Complete

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 vi dollars and weight wi pounds.
  • Take as valuable a load as possible, but cannot exceed W pounds.
  • vi wi W are integers.
  1. W ≤ capacity  
  2. 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:

KodNest 1 16

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.

KodNest 2 12
V [i, j] = max {V [i - 1, j], vi + V [i - 1, j -wi]
KodNest 3 11
KodNest 4 10

The value of V [3, 7] was computed as follows:

V [3, 7] = max {V [3 - 1, 7], v3 + V [3 - 1, 7 - w3]
         = max {V [2, 7], 18 + V [2, 7 - 5]}
         = max {7, 18 + 6}
         = 24
KodNest 5 10

Finally, the output is:

KodNest 6 7

The maximum value of items in the knapsack is 40, the bottom-right 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 (wi≤ w & vi + V [i-1, w -  wi]> V [i -1,W])
 7. then V [i, W] ←  vi + V [i - 1, w - wi]
 8. else V [i, W] ← V [i - 1, w]
KodNest Training New Batch is starting on 02nd November 2020. Attend one week free demo classes.Register Now

New Report

Close