贪心算法背包问题Python_贪心算法求解背包问题python?

问题描述解题思路代码

现有N个物品，背包容量W，各个物品的重量数组w[]，价值数组p[]。物品可选择部分装入，求背包价值最大的装法

由于物品可选择部分装入，该问题并非0-1背包问题，因此可选择贪心算法求解。将物品按单位重量的价值从大到小排序，依次装入背包。

// An highlighted block
N,W=[int(item) for item in input().split(' ')]
w=[]
p=[]
w_p=[]

for i in range(N):
    temp_w,temp_p=input().split(' ')
    w.append(int(temp_w))
    p.append(int(temp_p))
    w_p.append(int(temp_p)/int(temp_w))

for i in range(N):
    max_index=i
    for j in range(i+1,N):
        if w_p[j]>w_p[max_index]:
            max_index=j
    if max_index!=i:
        w_p[i], w_p[max_index] = w_p[max_index], w_p[i]
        w[i], w[max_index] = w[max_index], w[i]
        p[i],p[max_index]=p[max_index],p[i]

curr_w=0
index=0
max_p=0
while index