-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathZeroOneKnapsack.py
More file actions
28 lines (22 loc) · 806 Bytes
/
Copy pathZeroOneKnapsack.py
File metadata and controls
28 lines (22 loc) · 806 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Created by Roshan Jayswal
# Copyright © AppMillers. All rights reserved.
# Zero One Knapsack in Python
class Item:
def __init__(self, profit, weight):
self.profit = profit
self.weight = weight
def zoKnapsack(items, capacity, currentIndex):
if capacity <=0 or currentIndex < 0 or currentIndex >= len(items):
return 0
elif items[currentIndex].weight <= capacity:
profit1 = items[currentIndex].profit + zoKnapsack(items, capacity-items[currentIndex].weight, currentIndex+1)
profit2 = zoKnapsack(items, capacity, currentIndex+1)
return max(profit1, profit2)
else:
return 0
mango = Item(31, 3)
apple = Item(26, 1)
orange = Item(17, 2)
banana = Item(72, 5)
items = [mango, apple, orange, banana]
print(zoKnapsack(items, 7, 0))