有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑wi <= c1 + c2。问是否有一个合理的装载方案,可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。
如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题:
max∑ wi * xi && ∑ wi * xi <= c1, xi ∈ {0, 1}, 1 <= i <= n;
算法 L o a d i n g ( W , c 1 ) ?；
S o r t ( W )；
B ← c 1 ; b e s t ← c 1 ; i ← 1 ;
4 while?i ≤ n do
?? if 装入i ii后重量不超过c 1
?? then B ← B ? w i ; x [ i ] ← 1 ; i ← i + 1 ;
?? else x [ i ] ← 0 ; i ← i + 1 ;
if B <best
then记录解; b e s t ← B ;
Backtrack( i ) ;
if i = 1
then return 最优解
else goto 4.
首先按照物品体积进行排序，调用sort() 函数，其最优时间复杂度为O(n),最差时间复杂度为 O(n logn),平均时间复杂度为O(n logn), 其中按照 贪心策略寻找最优解的 for 语句的时间复杂度为均为 O(n),因此时间复杂度为 O(n+nlogn)。
[github源码地址]
原文：https://www.cnblogs.com/zs0618/p/14801783.html