贪心算法—装载及背包问题

装载问题和背包问题都是经典的贪心算法问题。装载问题是指有一批集装箱需要装载到船上，每个集装箱有自己的重量和体积，船有自己的载重量和容积限制，需要确定如何选择集装箱进行装载，使得船的载重量和容积限制最大化。背包问题是指有一批物品需要放入一个容量为V的背包中，每个物品有自己的重量和价值，需要确定如何选择物品放入背包中，使得背包中物品的总价值最大化。

装载问题和背包问题都具有贪心选择性质，即每次选择当前看起来最优的集装箱或物品。但是，背包问题还具有最优子结构性质，即子问题的最优解可以推导出原问题的最优解。因此，背包问题可以用贪心算法求解，而装载问题则不能。

下面是装载问题和背包问题的贪心算法实现：

装载问题：
假设船的载重量为C，有n个集装箱需要装载，每个集装箱的重量为wi。按照重量从大到小排序，依次选择集装箱进行装载，直到船的载重量达到C或者所有集装箱都已经装载完毕。

def loading_problem(C, w):
    w.sort(reverse=True)
    n = len(w)
    i = 0
    while C > 0 and i < n:
        if w[i] <= C:
            C -= w[i]
            i += 1
        else:
            break
    return i

背包问题：
假设有n个物品需要放入容量为V的背包中，每个物品的重量为wi，价值为vi。按照单位重量的价值从大到小排序，依次选择物品放入背包中，直到背包容量达到V或者所有物品都已经放入背包中。

def knapsack_problem(V, w, v):
    n = len(w)
    unit_value = [(v[i] / w[i], i) for i in range(n)]
    unit_value.sort(reverse=True)
    i = 0
    value = 0
    while V > 0 and i < n:
        j = unit_value[i][1]
        if w[j] <= V:
            V -= w[j]
            value += v[j]
            i += 1
        else:
            value += V * unit_value[i][0]
            V = 0
    return value