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 26 of 43
In Progress

Knapsack Problem

Fractions of items can be taken rather than having to make binary (0-1) choices for each item.

Fractional Knapsack Problem can be solvable by greedy strategy whereas 0 – 1 problem is not.

Steps to solve the Fractional Problem:

  1. Compute the value per pound  for each item.
  2. Obeying a Greedy Strategy, we take as possible of the item with the highest value per pound.
  3. If the supply of that element is exhausted and we can still carry more, we take as much as possible of the element with the next value per pound.
  4. Sorting, the items by value per pound, the greedy algorithm run in O (n log n) time.
Fractional Knapsack (Array v, Array w, int W)
1. for i= 1 to size (v)
2. do p [i] = v [i] / w [i]
3. Sort-Descending (p)
4. i ← 1
5. while (W>0)
6. do amount = min (W, w [i])
7. solution [i] = amount
8. W= W-amount
9. i ← i+1
10. return solution


Example: Consider 5 items along their respective weights and values: –

I = (I1,I2,I3,I4,I5)

w = (5, 10, 20, 30, 40)

v = (30, 20, 100, 90,160)

The capacity of knapsack W = 60

Now fill the knapsack according to the decreasing value of pi.

First, we choose the item Ii whose weight is 5.

Then choose item I3 whose weight is 20. Now,the total weight of knapsack is 20 + 5 = 25

Now the next item is I5, and its weight is 40, but we want only 35, so we chose the fractional part of it,

Fractional Knapsack Problem

Solution:

ITEMwivi
I1530
I21020
I320100
I43090
I540160
Fractional Knapsack Problem

Taking value per weight ratio i.e. pi=

ITEMwiviPi=
I15306.0
I210202.0
I3201005.0
I430903.0
I5401604.0

Now, arrange the value of pi in decreasing order.

ITEMwivipi=
I15306.0
I3201005.0
I5401604.0
I430903.0
I210202.0

New Report

Close