LNH_Sniper 发表于 2011-7-11 13:43:48

算法每日一题（八）——__贪心法

本帖最后由 LNH_Sniper 于 2011-7-11 19:57 编辑

问题： 有一批集装箱要装入一个质量为C的货船中，每个集装箱的质量由用户自己输入指定，在货船的装载体积不限的前提下，如何装载集装箱才能尽可能多的地将集装箱装入货船中。


Be_envious 发表于 2011-7-11 17:23:36

挺有意思的, 我没接触过这个算法

LNH_Sniper 发表于 2011-7-11 22:31:22

贪心法基本概念：
（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。
      

asd82937121 发表于 2011-7-12 09:52:59

能不能 写一小段程序 说明

Be_envious 发表于 2011-7-13 23:25:01

表示 可以理解

Be_envious 发表于 2011-7-20 23:03:34

又看了一遍 明白多了

紫色枫叶 发表于 2011-7-20 23:16:19

本来我想可以先排个序，后来仔细一想，还不可以，因为一旦排序后，箱子的编号就乱了。不知道是否可以这么做typedef struct box
{
    int weight;
    int num;
}Box;

x517302248 发表于 2014-6-3 19:16:42

需要LOOKLOOK。。。。。

lf19891031 发表于 2014-6-5 11:01:06

学习学习   很不错

wangerwanger 发表于 2014-8-1 12:36:40

最近那个微信神经猫说用的就是贪心算法

cable5881 发表于 2014-8-4 18:00:33

发个梵蒂冈地方个梵蒂冈地方

cable5881 发表于 2014-8-11 17:42:42

谢谢楼主分享！！！！！！！！！！

TheGod 发表于 2014-11-5 21:26:32

是动态规划吧

vanentu 发表于 2015-5-24 04:04:55

辛苦了辛苦了

vanentu 发表于 2015-5-24 04:06:25

ThanksFORshare

溯月0503 发表于 2015-5-24 10:05:48

{:1_1:}

2413780002 发表于 2015-5-24 16:44:11

挺有意思的

vank 发表于 2015-5-25 16:04:49

哇，看到这，我好兴奋:ton:

喵小乐cherry 发表于 2015-5-26 22:04:46

哈哈

waliemiao 发表于 2015-10-12 00:29:00

挺有意思的
页: [1] 2
查看完整版本: 算法每日一题（八）——__贪心法