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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#!/usr/bin/env python3
# Challenge 036
#
# TASK #2
# Write a program to solve Knapsack Problem.
# There are 5 color coded boxes with varying weights and amounts in GBP. Which
# boxes should be choosen to maximize the amount of money while still keeping
# the overall weight under or equal to 15 kgs?
#
# R: (weight = 1 kg, amount = 1)
# B: (weight = 1 kg, amount = 2)
# G: (weight = 2 kg, amount = 2)
# Y: (weight = 12 kg, amount = 4)
# P: (weight = 4 kg, amount = 10)
# Bonus task, what if you were allowed to pick only 2 boxes or 3 boxes or
# 4 boxes? Find out which combination of boxes is the most optimal?
from itertools import combinations
max_weigth = 15
class Box:
def __init__(self, color, weight, amount):
self.color = color
self.weight = weight
self.amount = amount
def __repr__(self):
return "Box("+ \
",".join([str(x) for x in \
[self.color, self.weight, self.amount]])+ \
")"
boxes = [
Box('R', 1, 1 ),
Box('B', 1, 2 ),
Box('G', 2, 2 ),
Box('Y', 12, 4 ),
Box('P', 4, 10 )
]
def solve(boxes):
max_amount = 0
max_combo = []
for k in range(1, len(boxes)+1):
for combo in list(combinations(boxes, k)):
weight = sum([x.weight for x in list(combo)])
amount = sum([x.amount for x in list(combo)])
if weight <= max_weigth:
if amount > max_amount:
max_amount = amount
max_combo = list(combo)
return max_combo
print("".join(sorted([x.color for x in solve(boxes)])))
|
