【贪心】最优装载问题Python实现

文章目录

• • @[toc]
  • • 问题描述
    • • 形式化描述
    • 贪心算法
    • • 贪心选择性质
      • 最优子结构性质
    • 时间复杂性
    • `Python`实现

问题描述

• 有一批集装箱要装上一艘载重量为$c$的轮船，其中集装箱$i$的重量为$w_i$
• 在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船

形式化描述

{ max ? ∑ i = 1 n x i ∑ i = 1 n w i x i ≤ c x i ∈ { ? 0 , 1 ? } , 1 ≤ i ≤ n \begin{cases} \max{\displaystyle\sum\limits_{i = 1}^{n}{x_{i}}} \\ \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c \end{cases} \kern{2em} x_{i} \in \set{0 , 1} , 1 \leq i \leq n ? ? ??maxi=1∑n?xi?i=1∑n?wi?xi?≤c?xi?∈{0,1},1≤i≤n

贪心算法

• 采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解

贪心选择性质

• 设集装箱已依其重量从小到大排序，$(x_1,x_2,?,x_n)$是最优装载问题的一个最优解，设 k = min ? 1 ≤ i ≤ n { ? i ∣ x i = 1 ? } k = \min\limits_{1 \leq i \leq n}{\set{i \mid x_{i} = 1}} k=1≤i≤nmin?{i∣xi?=1}，如果给定的最优装载问题有解，则$1\le k\le n$
  • 当$k=1$时，$(x_1,x_2,?,x_n)$是一个满足贪心选择性质的最优解
  • 当$k>1$时，取$y_1=1$，$y_k=0$，$y_i=x_i$，$1<j\le n$，$i\ne k$，则$\sum _{i=1}^n{w}_i{y}_i=w_1?w_k+\sum _{i=1}^n{w}_i{x}_i\le \sum _{i=1}^n{w}_i{x}_i\le c$，因此，$(y_1,y_2,?,y_n)$是所给最优装载问题的可行解
• 由$\sum _{i=1}^n{y}_i=\sum _{i=1}^n{x}_i$知，$(y_1,y_2,?,y_n)$是满足贪心选择性质的最优解，所以，最优装载问题具有贪心选择性质

最优子结构性质

• 设$(x_1,x_2,?,x_n)$是最优装载问题的满足贪心选择性质的最优解，则$x_1=1$，$(x_2,x_3,?,x_n)$是轮船载重量为$c?w_1$、待装船集装箱为 { ? 2 , 3 , ? ? , n ? } \set{2 , 3 , \cdots , n} {2,3,?,n}时相应最优装载问题的最优解，也就是说，最优装载问题具有最优子结构性质

时间复杂性

• 算法的主要计算量在于将集装箱依其重量从小到大排序，所以算法所需的计算时间为$O(n\log n)$

Python实现

def load_ship(containers, capacity):
    # 将集装箱组织成 (索引, 重量) 二元组形式
    containers = list(enumerate(containers))

    # 按照集装箱的重量进行排序
    containers.sort(key=lambda x: x[1])

    # 记录已经装载的集装箱索引
    loaded_containers = []
    # 记录当前已经装载的总重量
    current_weight = 0

    # 遍历每个集装箱
    for index, weight in containers:
        # 如果当前集装箱的重量加上已经装载的总重量不超过轮船的载重量, 则将集装箱装上轮船
        if current_weight + weight <= capacity:
            current_weight += weight

            loaded_containers.append(index)
        else:
            # 如果无法装载当前集装箱, 则退出循环
            break

    loaded_containers.sort()

    return loaded_containers


containers = [3, 5, 2, 7, 4, 1]
capacity = 10

res = load_ship(containers, capacity)

print(f'装载的集装箱索引: {res}')

装载的集装箱索引: [0, 2, 4, 5]