【贪心算法的背包问题】python

贪心算法与01的区别就是：
（1）贪心可以取物品的部分放入背包，01只有取或不取两种结果
（2）由（1）导致贪心需要在“背包容量”情况下，找到每单位重量价值尽量大的物品，这也是排序的意义所在

def greedy_backage(w, v, backage):
    # 贪心背包问题
    li = [0]
    for i in range(1, len(w)):
        # 按照 价值/重量 的价值比重新降序排序
        # 优化就优化这里
        temp = v[i] / w[i]
        j = 0
        while j < len(li):
            if temp < v[li[j]] / w[li[j]]:
                j += 1
            else:
                li.insert(j, i)
                break
        if j == len(li):
            li.append(i)
    print('物品每单位重量价值降序排序: ',li)
    max_v = 0
    for i in range(len(li)):
        if backage >= w[li[i]]:
            backage -= w[li[i]]
            max_v += v[li[i]]
        else:
            max_v += (backage / w[li[i]]) * v[li[i]]
            break
    return max_v


if __name__ == '__main__':
    weights = [20, 30, 10]
    values = [60, 120, 50]
    backage = 50
    res = greedy_backage(weights, values, backage)
    print('贪心算法下背包问题结果为: ', res)

与01算法下的结果比较