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

文章目录

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

个人主页：丷从心

系列专栏：贪心算法

问题描述

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

形式化描述

$\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$

贪心算法

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

贪心选择性质

设集装箱已依其重量从小到大排序， $(x_{1} , x_{2} , \cdots , x_{n})$ 是最优装载问题的一个最优解，设 $\min\limits_{1 \leq i \leq n}{\set{i \mid x_{i} = 1}}$ ，如果给定的最优装载问题有解，则 $\leq k \leq n$
- 当 $k = 1$ 时， $(x_{1} , x_{2} , \cdots , x_{n})$ 是一个满足贪心选择性质的最优解
- 当 $k > 1$ 时，取 $y_{1} = 1$ ， $y_{k} = 0$ ， $y_{i} = x_{i}$ ， $\leq n$ ， $\neq k$ ，则 $\displaystyle\sum\limits_{i = 1}^{n}{w_{i} y_{i}} = w_{1} - w_{k} + \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c$ ，因此， $(y_{1} , y_{2} , \cdots , y_{n})$ 是所给最优装载问题的可行解
由 $\displaystyle\sum\limits_{i = 1}^{n}{y_{i}} = \displaystyle\sum\limits_{i = 1}^{n}{x_{i}}$ 知， $(y_{1} , y_{2} , \cdots , y_{n})$ 是满足贪心选择性质的最优解，所以，最优装载问题具有贪心选择性质

最优子结构性质

设 $(x_{1} , x_{2} , \cdots , x_{n})$ 是最优装载问题的满足贪心选择性质的最优解，则 $x_{1} = 1$ ， $(x_{2} , x_{3} , \cdots , x_{n})$ 是轮船载重量为 $c - w_{1}$ 、待装船集装箱为 $\set{2 , 3 , \cdots , 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}')