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

本文主要是介绍【贪心算法】【Python实现】最优装载问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

@[toc]
问题描述
形式化描述

贪心算法
贪心选择性质
最优子结构性质

`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}$ 时相应最优装载问题的最优解，也就是说，最优装载问题具有最优子结构性质

`Python`实现

def loading_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 += weightloaded_containers.append(index)else:# 如果无法装载当前集装箱, 则退出循环breakloaded_containers.sort()return loaded_containerscontainers = [3, 5, 2, 7, 4, 1]
capacity = 10res = loading_ship(containers, capacity)print(f'装载的集装箱索引: {res}')