# knapsack problem

Views:

Category: Education

## Presentation Description

No description available.

## 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

Jewellary shop

Store room

### Slide 6:

Items Jewellary Items

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)

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

Thank You