56做视频网站,上海有名的网站建设公司,视频直播技术,建设企业网站的目的文章目录 [toc]问题描述形式化描述 贪心算法贪心选择性质最优子结构性质 Python实现时间复杂性 问题描述
有一批集装箱要装上一艘载重量为 c c c的轮船#xff0c;其中集装箱 i i i的重量为 w i w_{i} wi在装载体积不受限制的情况下#xff0c;将尽可能多的集装箱装上轮船… 文章目录 [toc]问题描述形式化描述 贪心算法贪心选择性质最优子结构性质 Python实现时间复杂性
问题描述
有一批集装箱要装上一艘载重量为 c c c的轮船其中集装箱 i i i的重量为 w i w_{i} wi在装载体积不受限制的情况下将尽可能多的集装箱装上轮船
形式化描述 { 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 ⎩ ⎨ ⎧maxi1∑nxii1∑nwixi≤cxi∈{0,1},1≤i≤n 贪心算法
采用重量最轻者先装的贪心选择策略可产生最优装载问题的最优解
贪心选择性质
设集装箱已依其重量从小到大排序 ( x 1 , x 2 , ⋯ , x n ) (x_{1} , x_{2} , \cdots , x_{n}) (x1,x2,⋯,xn)是最优装载问题的一个最优解设 k min 1 ≤ i ≤ n { i ∣ x i 1 } k \min\limits_{1 \leq i \leq n}{\set{i \mid x_{i} 1}} k1≤i≤nmin{i∣xi1}如果给定的最优装载问题有解则 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤n 当 k 1 k 1 k1时 ( x 1 , x 2 , ⋯ , x n ) (x_{1} , x_{2} , \cdots , x_{n}) (x1,x2,⋯,xn)是一个满足贪心选择性质的最优解当 k 1 k 1 k1时取 y 1 1 y_{1} 1 y11 y k 0 y_{k} 0 yk0 y i x i y_{i} x_{i} yixi 1 i ≤ n 1 i \leq n 1i≤n i ≠ k i \neq k ik则 ∑ i 1 n w i y i w 1 − w k ∑ i 1 n w i x i ≤ ∑ i 1 n w i x i ≤ c \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 i1∑nwiyiw1−wki1∑nwixi≤i1∑nwixi≤c因此 ( y 1 , y 2 , ⋯ , y n ) (y_{1} , y_{2} , \cdots , y_{n}) (y1,y2,⋯,yn)是所给最优装载问题的可行解 由 ∑ i 1 n y i ∑ i 1 n x i \displaystyle\sum\limits_{i 1}^{n}{y_{i}} \displaystyle\sum\limits_{i 1}^{n}{x_{i}} i1∑nyii1∑nxi知 ( y 1 , y 2 , ⋯ , y n ) (y_{1} , y_{2} , \cdots , y_{n}) (y1,y2,⋯,yn)是满足贪心选择性质的最优解所以最优装载问题具有贪心选择性质
最优子结构性质
设 ( x 1 , x 2 , ⋯ , x n ) (x_{1} , x_{2} , \cdots , x_{n}) (x1,x2,⋯,xn)是最优装载问题的满足贪心选择性质的最优解则 x 1 1 x_{1} 1 x11 ( x 2 , x 3 , ⋯ , x n ) (x_{2} , x_{3} , \cdots , x_{n}) (x2,x3,⋯,xn)是轮船载重量为 c − w 1 c - w_{1} c−w1、待装船集装箱为 { 2 , 3 , ⋯ , n } \set{2 , 3 , \cdots , n} {2,3,⋯,n}时相应最优装载问题的最优解也就是说最优装载问题具有最优子结构性质 Python实现
def loading_ship(containers, capacity):# 将集装箱组织成 (索引, 重量) 二元组形式containers list(enumerate(containers))# 按照集装箱的重量进行排序containers.sort(keylambda 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})装载的集装箱索引: [0, 2, 4, 5]时间复杂性
算法的主要计算量在于将集装箱依其重量从小到大排序所以算法所需的计算时间为 O ( n log n ) O(n \log{n}) O(nlogn)
