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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 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[2] = 5, 就表示第 2 个集装箱的质量为 5。再设置一个向量数组 x[]存放集装箱的取舍状态。其中，x[i] = 1 表示将第 i 个集装箱放入船中，x[i] = 0 表示第 i 个集装箱不装入货船。最终输出的结果应当是向量数组x[]的下标，如果输出结果为{ 0, 1, 4, 5 }表示将第 0, 1 , 4, 5个集装箱装入货船中。也就是输出数组 x[] 中所有  x[ i ] = 1 的下标 i。
   应用贪心算法求解，每次都要选出数组 w[]中当前质量最轻的( 即 w[i] 值最小的 ) 集装箱，并将 x[i]置 1，同时  c = c - w[i]，即变量  c 中存放货船已达到最大载质量，或者集装箱完全装完为止。然后输出数组x[]中所有x[i] = 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[5];

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

挺有意思的

账号		自动登录	找回密码
密码			立即注册

[争议讨论] 算法每日一题（八）——__贪心法

马上注册，结交更多好友，享用更多功能^_^