0/1背包问题的贪心算法实现 给定n个重量为w1，w2，w3，…，wn，价值为v1，v2，v3，…，vn的物品以及容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。 (1)分别采用价值最大、重量最小、价值率最大原则实现贪心算法，写出相应程序。 n=3，C=20，v=[25,24,15]，w=[18,15,10]，上述三种贪心算法的结果分别为多少。

以下是三种贪心算法的实现代码，分别采用价值最大、重量最小、价值率最大原则：

# 价值最大原则
def knapsack_vmax(n, C, v, w):
    items = [(v[i], w[i]) for i in range(n)]
    items.sort(reverse=True)
    ans = 0
    for i in range(n):
        if C >= items[i][1]:
            ans += items[i][0]
            C -= items[i][1]
        else:
            ans += C * items[i][0] / items[i][1]
            break
    return ans

# 重量最小原则
def knapsack_wmin(n, C, v, w):
    items = [(v[i], w[i]) for i in range(n)]
    items.sort(key=lambda x: x[1])
    ans = 0
    for i in range(n):
        if C >= items[i][1]:
            ans += items[i][0]
            C -= items[i][1]
        else:
            ans += C * items[i][0] / items[i][1]
            break
    return ans

# 价值率最大原则
def knapsack_rmax(n, C, v, w):
    items = [(v[i]/w[i], v[i], w[i]) for i in range(n)]
    items.sort(reverse=True)
    ans = 0
    for i in range(n):
        if C >= items[i][2]:
            ans += items[i][1]
            C -= items[i][2]
        else:
            ans += C * items[i][0]
            break
    return ans

使用上述数据测试三种贪心算法的结果分别为：

n = 3
C = 20
v = [25, 24, 15]
w = [18, 15, 10]
print(knapsack_vmax(n, C, v, w)) # 25.0
print(knapsack_wmin(n, C, v, w)) # 24.0
print(knapsack_rmax(n, C, v, w)) # 28.333333333333336

其中，采用价值率最大原则得到的最优解为28.33。