FilesExpand file tree

Write-for-current-Python

/

greedy_knapsack.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

98 lines (83 loc) · 3.62 KB

Write-for-current-Python

/

greedy_knapsack.py

Copy path

Top

File metadata and controls

• Code
• Blame

98 lines (83 loc) · 3.62 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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

# To get an insight into Greedy Algorithm through the Knapsack problem

"""

A shopkeeper has bags of wheat that each have different weights and different profits.

eg.

profit 5 8 7 1 12 3 4

weight 2 7 1 6 4 2 5

max_weight 100

Constraints:

max_weight > 0

profit[i] >= 0

weight[i] >= 0

Calculate the maximum profit that the shopkeeper can make given maxmum weight that can

be carried.

"""

def calc_profit(profit: list, weight: list, max_weight: int) -> int:

"""

Function description is as follows-

:param profit: Take a list of profits

:param weight: Take a list of weight if bags corresponding to the profits

:param max_weight: Maximum weight that could be carried

:return: Maximum expected gain

>>> calc_profit([1, 2, 3], [3, 4, 5], 15)

6

>>> calc_profit([10, 9 , 8], [3 ,4 , 5], 25)

27

"""

if len(profit) != len(weight):

raise ValueError("The length of profit and weight must be same.")

if max_weight <= 0:

raise ValueError("max_weight must greater than zero.")

if any(p < 0 for p in profit):

raise ValueError("Profit can not be negative.")

if any(w < 0 for w in weight):

raise ValueError("Weight can not be negative.")

# List created to store profit gained for the 1kg in case of each weight

# respectively. Calculate and append profit/weight for each element.

profit_by_weight = [p / w for p, w in zip(profit, weight)]

# Creating a copy of the list and sorting profit/weight in ascending order

sorted_profit_by_weight = sorted(profit_by_weight)

# declaring useful variables

length = len(sorted_profit_by_weight)

limit = 0

gain = 0

i = 0

# loop till the total weight do not reach max limit e.g. 15 kg and till i<length

while limit <= max_weight and i < length:

# flag value for encountered greatest element in sorted_profit_by_weight

biggest_profit_by_weight = sorted_profit_by_weight[length - i - 1]

"""

Calculate the index of the biggest_profit_by_weight in profit_by_weight list.

This will give the index of the first encountered element which is same as of

biggest_profit_by_weight. There may be one or more values same as that of

biggest_profit_by_weight but index always encounter the very first element

only. To curb this alter the values in profit_by_weight once they are used

here it is done to -1 because neither profit nor weight can be in negative.

"""

index = profit_by_weight.index(biggest_profit_by_weight)

profit_by_weight[index] = -1

# check if the weight encountered is less than the total weight

# encountered before.

if max_weight - limit >= weight[index]:

limit += weight[index]

# Adding profit gained for the given weight 1 ===

# weight[index]/weight[index]

gain += 1 * profit[index]

else:

# Since the weight encountered is greater than limit, therefore take the

# required number of remaining kgs and calculate profit for it.

# weight remaining / weight[index]

gain += (max_weight - limit) / weight[index] * profit[index]

break

i += 1

return gain

if __name__ == "__main__":

print(

"Input profits, weights, and then max_weight (all positive ints) separated by "

"spaces."

)

profit = [int(x) for x in input("Input profits separated by spaces: ").split()]

weight = [int(x) for x in input("Input weights separated by spaces: ").split()]

max_weight = int(input("Max weight allowed: "))

# Function Call

calc_profit(profit, weight, max_weight)