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 maxweight 100 constraints maxweight 0 profiti 0 weighti 0 calculate the maximum profit that the shopkeeper can make given maxmum weight that can be carried 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 maxweight maximum weight that could be carried return maximum expected gain calcprofit1 2 3 3 4 5 15 6 calcprofit10 9 8 3 4 5 25 27 list created to store profit gained for the 1kg in case of each weight respectively calculate and append profitweight for each element creating a copy of the list and sorting profitweight in ascending order declaring useful variables loop till the total weight do not reach max limit e g 15 kg and till ilength flag value for encountered greatest element in sortedprofitbyweight calculate the index of the biggestprofitbyweight in profitbyweight list this will give the index of the first encountered element which is same as of biggestprofitbyweight there may be one or more values same as that of biggestprofitbyweight but index always encounter the very first element only to curb this alter the values in profitbyweight once they are used here it is done to 1 because neither profit nor weight can be in negative check if the weight encountered is less than the total weight encountered before adding profit gained for the given weight 1 weightindexweightindex since the weight encountered is greater than limit therefore take the required number of remaining kgs and calculate profit for it weight remaining weightindex function call 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 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 list created to store profit gained for the 1kg in case of each weight respectively calculate and append profit weight for each element creating a copy of the list and sorting profit weight in ascending order declaring useful variables loop till the total weight do not reach max limit e g 15 kg and till i length flag value for encountered greatest element in sorted_profit_by_weight 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 check if the weight encountered is less than the total weight encountered before adding profit gained for the given weight 1 weight index weight index 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 function call
def calc_profit(profit: list, weight: list, max_weight: int) -> int:
    
    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.")

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

    
    sorted_profit_by_weight = sorted(profit_by_weight)

    
    length = len(sorted_profit_by_weight)
    limit = 0
    gain = 0
    i = 0

    
    while limit <= max_weight and i < length:
        
        biggest_profit_by_weight = sorted_profit_by_weight[length - i - 1]
        
        index = profit_by_weight.index(biggest_profit_by_weight)
        profit_by_weight[index] = -1

        
        
        if max_weight - limit >= weight[index]:
            limit += weight[index]
            
            
            gain += 1 * profit[index]
        else:
            
            
            
            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: "))

    
    calc_profit(profit, weight, max_weight)