[ 问题描述 ] 输入 :(x1,x2,...xn), xi=0, 货箱 i 不装船 ; xi=1, 货箱 i
装船
可行解 : 满足约束条件 ≤ c 的输入
优化函数 :
最优解 : 使优化函数达到最大值的一种输入 .
i
n
i
i
xw
1
n
i
i
x
1
4.3 最优装载
算法设计与分析 > 贪心算法
[ 例 ]
设 n=8 , [w1 …, w8]=[100, 200, 50, 90, 150, 50, 20,
80] , c=400 。
所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2 。货箱 7, 3, 6, 8, 4, 1 的
总重量为 390 个单位且已被装载 , 剩下的装载能力为 10 , 小于任
意
货箱 . 所以得到解 [x1,...x8]=[ 1, 0, 1, 1, 0, 1, 1, 1]
[ 算法思路 ] 将装船过程划为多步选择,每步装一个货箱,每次
从剩下的货箱中选择重量最轻的货箱 . 如此下去直到所有货箱均
装上船或船上不能再容纳其他任何一个货箱。