有一批集装箱要装上一艘载重量为
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
????maxi=1∑n?xi?i=1∑n?wi?xi?≤c?xi?∈{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}}
k=1≤i≤nmin?{i∣xi?=1}，如果给定的最优装载问题有解，则
1
≤
k
≤
n
1 \leq k \leq n
1≤k≤n
当
k
=
1
k = 1
k=1时，
(
x
1
,
x
2
,
?
?
,
x
n
)
(x_{1} , x_{2} , \cdots , x_{n})
(x1?,x2?,?,xn?)是一个满足贪心选择性质的最优解
当
k
>
1
k > 1
k>1时，取
y
1
=
1
y_{1} = 1
y1?=1，
y
k
=
0
y_{k} = 0
yk?=0，
y
i
=
x
i
y_{i} = x_{i}
yi?=xi?，
1
<
j
≤
n
1 < j \leq n
1<j≤n，
i
≠
k
i \neq k
i=k，则
∑
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
i=1∑n?wi?yi?=w1??wk?+i=1∑n?wi?xi?≤i=1∑n?wi?xi?≤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}}
i=1∑n?yi?=i=1∑n?xi?知，
(
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
x1?=1，
(
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}时相应最优装载问题的最优解，也就是说，最优装载问题具有最优子结构性质
时间复杂性
算法的主要计算量在于将集装箱依其重量从小到大排序，所以算法所需的计算时间为
O
(
n
log
?
n
)
O(n \log{n})
O(nlogn)