FilesExpand file tree

 patch-1

/

knapsack.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

47 lines (37 loc) · 1.4 KB

 patch-1

/

knapsack.py

Top

File metadata and controls

• Code
• Blame

47 lines (37 loc) · 1.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

from typing import List

""" A naive recursive implementation of 0-1 Knapsack Problem

https://en.wikipedia.org/wiki/Knapsack_problem

"""

def knapsack(capacity: int, weights: List[int], values: List[int], counter: int) -> int:

"""

Returns the maximum value that can be put in a knapsack of a capacity cap,

whereby each weight w has a specific value val.

>>> cap = 50

>>> val = [60, 100, 120]

>>> w = [10, 20, 30]

>>> c = len(val)

>>> knapsack(cap, w, val, c)

220

The result is 220 cause the values of 100 and 120 got the weight of 50

which is the limit of the capacity.

"""

# Base Case

if counter == 0 or capacity == 0:

return 0

# If weight of the nth item is more than Knapsack of capacity,

# then this item cannot be included in the optimal solution,

# else return the maximum of two cases:

# (1) nth item included

# (2) not included

if weights[counter - 1] > capacity:

return knapsack(capacity, weights, values, counter - 1)

else:

left_capacity = capacity - weights[counter - 1]

new_value_included = values[counter - 1] + knapsack(

left_capacity, weights, values, counter - 1

)

without_new_value = knapsack(capacity, weights, values, counter - 1)

return max(new_value_included, without_new_value)

if __name__ == "__main__":

import doctest

doctest.testmod()