贪婪背包算法

Question

任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。

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是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。

Answer 1

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)