Greedy knapsack algorithm

user_12962634 0
Viewed 211

The task is classic knapsack problem. Greedy algorithm should be used in solvation. I managed to create code below, but it works too slow. Could you give me an idea how to speed it up? Thank you.

def backpack(c, array):
    array.sort(key=lambda x: x[1])
    array.sort(key=lambda x: x[0], reverse=True)
    backpack = []

    for item in array:
        if item[1] <= c:
            backpack.append(item)
            c -= item[1]

    result = []
    for item in backpack:
        result.append(item[2])
    result.sort()

    return print(*result)


c = int(input())
n = int(input())
array = list()
for i in range(n):
    item = [int(x) for x in input().split()]
    array.append(item)
    array[i].append(i)

backpack(c, array)

c is weight limit for backpack. n represents the amount of price-weight pairs (both numbers have int type, not float). Restrictions are following: 1) should you choose between elements with the same weight, the one with the highest price should be taken 2) should you choose between elements with the same price and same weight, the one which was inputed first should be taken.

knapsack-problem greedy python
2 Answers

We can use:

def backpack(weight, arr):
    # Associate the index with each pair of the given array.
    arr = [(idx, pair) for idx, pair in enumerate(arr)]

    # sort the arr in descending order with highest price taking precedence
    arr = sorted(arr, reverse=True, key=lambda x: x[1][0]) 

    result, totalWeight = [], 0
    for item in arr:
        if item[1][1] + totalWeight <= weight:
            totalWeight += item[1][1] # increase the cummalative weight of backpack

            result.append(item[0]) # Append the index of added pair to result
    return result

Example:

# arr contains the pairs of <price, weight>
arr = [[1, 2], [2, 3], [1, 1], [2, 4], [2, 3], [5, 1], [1, 5], [3, 3], [2, 2]]
weight = 7
print(backpack(weight, arr))

Result:

[5, 7, 1] # indices of pairs in arr which are taken from array and added to backpack
user_128331660 
def backpack(c, array):
    array.sort(key=lambda x: x[2], reverse=True)
    print(array)
    result = 0
    for item in array:
        if c-item[1] >= 0:
            c=c-item[1]
            result=result+item[0]
        else:
            fraction = c/float(item[1])
            print(fraction)
            result+=(item[0]*fraction)
            break

    return result


c = int(input())
n = int(input())
array = []
for i in range(n):
    item = tuple(int(x) for x in raw_input().split())
    array.append(item+(item[0]//item[1],))
backpack(c, array)
user_24475870
Related