knapsack problem

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Problem Statement  A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith  item weigh wi and is worth vi lacs. What items should thief take? : 

Using Dynamic Programming Method Problem Statement  A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith  item weigh wi and is worth vi lacs. What items should thief take?

Slide 2: 

Dynamic Programming Solution to the 0-1 Knapsack Problem Submitted by - Kundan - Groups leader (Imran,Rishu,Asrish) M.C.A (2nd Sem)

Slide 3: 

Types of Knapsack Problem Implementation 1) Using Greedy Method 2) Using Dynamic Programming Method 3) Using Branch and Bound Method (B) Using Unbound Method (A) Using Bound Method

Slide 4: 

Jewellary shop

Slide 5: 

Store room

Slide 6: 

Items Jewellary Items

Slide 7: 

Entry of Thief

Slide 8: 

Looking for Valuable Items

Slide 9: 

Thief with his bag..

Slide 10: 

Size = 12 The Total Capacity of bag..

Slide 11: 

Burglary in process…

Slide 12: 

Burglary in process…

Slide 13: 

Burglary in process…

Slide 14: 

Burglary in process…

Slide 15: 

Burglary in process…

Slide 16: 

Burglary in process…

Slide 17: 

Burglary in process…

Slide 18: 

Burglary in process…

Slide 19: 

Burglary in process…

Slide 20: 

Burglary in process…

Slide 21: 

Burglary process is over…

Status of store stock : 

Status of store stock

Slide 25: 

3 Weight Items names values 5 6 7 2 8 21 23 32 3

Slide 26: 

Solution Table for the 0-1 Knapsack Problem

Structure of Solution Table.. : 

Structure of Solution Table.. Items/Weights

Structure of Solution Table.. : 

Structure of Solution Table.. GOLD SILVER DIAMOND PLATINUM MIXED ITEM

Slide 29: 

(W –V) Structure of Solution Table.. -

Status For One Item.. : 

Status For One Item.. (W –V)

Status For Two Items.. : 

Status For Two Items.. (W –V)

Status For Three Items.. : 

Status For Three Items.. (W –V)

Status For Four Items.. : 

Status For Four Items.. (W –V)

Status For Five Items.. : 

Status For Five Items.. (W –V)

Slide 35: 

Optimal Solution Status For Optimal Solution.. (W –V)

Slide 36: 

Optimal Solution

Status for maximum profit : 

Status for maximum profit

Slide 40: 

0 Weight Items names values 5 0 7 0 0 21 0 32 0

Slide 41: 

Maximum Profit -53

Slide 42: 

Thank You

authorStream Live Help