-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathknapsack using greedy algorithm
38 lines (28 loc) · 1.05 KB
/
knapsack using greedy algorithm
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
29
30
31
32
33
34
35
36
37
38
#knapsack problem using greedy method
class Sack:
def __init__(self,weight,profit,index):
self.weight=weight
self.profit=profit
self.index=index
self.profitperkg=profit//weight
def __lt__(self,other):
return self.profitperkg<other.profitperkg
class knapsack:
def appendingvalue(self,weight,profit,capacity):
value=[]
for i in range(len(weight)):
value.append(Sack(weight[i],profit[i],i))
value.sort(reverse=True)
total_value=0
for position in value:
currentweight=int(position.weight)
currentprofit=int(position.profit)
if capacity-currentweight>=0:
capacity -=currentweight
total_value +=currentprofit
else:
fraction=capacity/currentweight
total_value+=fraction*currentprofit
capacity-=int(fraction*currentweight)
break
return total_value