算法每日一题(八)——__贪心法
本帖最后由 LNH_Sniper 于 2011-7-11 19:57 编辑问题: 有一批集装箱要装入一个质量为C的货船中,每个集装箱的质量由用户自己输入指定,在货船的装载体积不限的前提下,如何装载集装箱才能尽可能多的地将集装箱装入货船中。
挺有意思的, 我没接触过这个算法 贪心法基本概念:
(1)贪心选择性质:就是指所求解问题的整体最优解可以通过一系列的局部最优解得到。所谓局部最优解,就是指在当前的状态下做出的最好选择。
(2)最优子结构性质:当一个问题的最优解包含着它的子问题的最优解时,就称此问题具有最优子结构性质。
具备以上两种性质,就可以通过贪心法求解。
对本题分析:
这个问题可以用贪心法求得最优解。只要每次装船时,采取质量最轻的集装箱先装船的策略,就可以得到最优装船问题的一个最优解。
在设计算法时,可用一个数组w[]存放每个集装箱的质量,例如w = 5, 就表示第 2 个集装箱的质量为 5。再设置一个向量数组 x[]存放集装箱的取舍状态。其中,x = 1 表示将第 i 个集装箱放入船中,x = 0 表示第 i 个集装箱不装入货船。最终输出的结果应当是向量数组x[]的下标,如果输出结果为{ 0, 1, 4, 5 }表示将第 0, 1 , 4, 5个集装箱装入货船中。也就是输出数组 x[] 中所有x[ i ] = 1 的下标 i。
应用贪心算法求解,每次都要选出数组 w[]中当前质量最轻的( 即 w 值最小的 ) 集装箱,并将 x置 1,同时c = c - w,即变量c 中存放货船已达到最大载质量,或者集装箱完全装完为止。然后输出数组x[]中所有x = 1 的下标 i。
能不能 写一小段程序 说明 表示 可以理解 又看了一遍 明白多了 本来我想可以先排个序,后来仔细一想,还不可以,因为一旦排序后,箱子的编号就乱了。不知道是否可以这么做typedef struct box
{
int weight;
int num;
}Box; 需要LOOKLOOK。。。。。 学习学习 很不错 最近那个微信神经猫说用的就是贪心算法 发个梵蒂冈地方个梵蒂冈地方 谢谢楼主分享!!!!!!!!!! 是动态规划吧 辛苦了辛苦了 ThanksFORshare {:1_1:} 挺有意思的 哇,看到这,我好兴奋:ton: 哈哈 挺有意思的
页:
[1]
2