18
回答
再问 石头过河问题--最少需要运多少次
滴滴云服务器,限时包月0.9元,为开发者而生>>>   

以前问过类似问题,没有很好解答。所以想再问一次。

有大大小小的一堆石头要用船拉到河对岸
--石头有m块,每块的重量已知
--船每次只能装k块石头,并且装载重量不可以超过w
--想求出最少几趟能把全部石头运过河。

 ------------------------------------
例1
 石头有9块,重量分别是1,2,3,4,5,6,7,8,9
k=3
w=15
那么结果是,最少3次就可以运完。
 ------------------------------------
 例2
 石头有9块,重量分别是1,1,1,5,6,6,7,9,9
k=3
w=15
那么结果是,最少 4 次才可以运完。
 ------------------------------------

<无标签>
举报
wsg
发帖于5年前 18回/887阅
共有18个答案 最后回答: 5年前
贪心算法搞定
--- 共有 3 条评论 ---
wsg回复 @风追云影 : 谢谢回复啊。我有考虑过贪心算法,但是,可能是我考虑的不深不周到。我发现贪心算法没能解决这个问题。 你能不能再给我详细地说一下呢? 5年前 回复
风追云影回复 @wsg : 是贪心算法 写错了不好意思 5年前 回复
wsg你好,我用背包问题解了很久,还是没有搞定。 这好像不是背包问题,而是多背包问题。难度不属于一个等级。 5年前 回复
如果最少的话,应当是m%k==0 ? m/k ? m/k +1次吧.
--- 共有 4 条评论 ---
wsg回复 @Hyacinthus_M : 是想计算在已经知道了各个参数的具体值以后的最小次数。 我在题里面加了例子,可能会比较好理解了。 5年前 回复
Hyacinthus_M@wsg 假设每块石头的重量依次为m1,m2,...,mn.那么石头的总质量则为M,那么这就是个简单的背包问题了. 5年前 回复
Hyacinthus_M@wsg 你都说最少了?既然对每块石头的重量都是未知的,只能将它看求最理想的情况下的解,即是最小解. 5年前 回复
wsg还有个限制条件的--装载重量不可以超过w 5年前 回复

动态规划吧... 

子解 是求 每次 运的石头总重量最大就行了.

--- 共有 4 条评论 ---
wsg回复 @酒逍遥 : 数量最多也不行啊。还是例1,如果取个子解为1,2,3一起运,也会导致整体运送次数增多 5年前 回复
酒逍遥回复 @wsg : 好像也不行.. 5年前 回复
酒逍遥回复 @wsg : 确实, 子解不成立. 那么子解为每次运送最多数量的石头呢? 5年前 回复
wsg上面的例1,如果取得某个子解为8和9一起运。虽然这个子解本身是最优,但是他导致整体运送次数至少多了一次。 5年前 回复
以贫道看来,将所有方法进行排列组合,写入到数据库中,然后select出次数最小的,绝对是最优解
--- 共有 2 条评论 ---
wsg回复 @wsg : 当然,这个如果能够等到结果,那肯定是最优解 5年前 回复
wsg这个太暴力,所有方法写出来的话,我的机器会累死,我也会等结果等到死的。 5年前 回复
只要保证在 质量 < w的情况下,尽可能多的数量个石头,就肯定是最优解了
--- 共有 2 条评论 ---
艾米回复 @wsg : 哦,我看走眼了,还有数量限制啊 5年前 回复
wsg这样不一定啊。 比如上面的例1,如果取个子解为1,2,3一起运,也会导致整体运送次数增多 5年前 回复

例1

第一船:123->129->189->179->169->159,等于15停止,剩余234678

第二船:234->238->278->268->248->348(4到3,非2到3)

例2

第一船:111->119->199->179->169->169->159,等于15停止,剩余116679

第二船:116->119->179->169->169->119,剩余667

第三船:667->67,当最轻的3块超过15优先去掉最轻的


提供一种思路,可能有思考不到的情况,没有大量数据实践得不出真理


--- 共有 1 条评论 ---
wsg虽然还没有最终验证,但是感觉这个方法挺不错!O(∩_∩)O谢谢 5年前 回复
顶部