Consider a Knapsack instance: Number of objects (n) = 4, Weights (wi) = {15, 10, 9, 5}, Profits (Pi) = {1, 5, 3, 4} and Knapsack Capacity (W) = 8 kg. Use greedy, dynamic approach and B&B technique to find the solution of this problem. code example

Example: greedy knapsack

def greedy_knapsack(values,weights,capacity):
    n = len(values)
    def score(i) : return values[i]/weights[i]
    items = sorted(range(n)  , key=score , reverse = True)
    sel, value,weight = [],0,0
    for i in items:
        if weight +weights[i] <= capacity:
            sel += [i]
            weight += weights[i]
            value += values [i]
    return sel, value, weight


weights = [4,9,10,20,2,1]
values = [400,1800,3500,4000,1000,200]
capacity = 20

print(greedy_knapsack(values,weights,capacity))