再问 石头过河问题--最少需要运多少次

wsg 发布于 2013/05/29 08:01
阅读 1K+
收藏 2

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

有大大小小的一堆石头要用船拉到河对岸
--石头有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 次才可以运完。
 ------------------------------------

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

动态规划吧... 

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

wsg
wsg
回复 @酒逍遥 : 数量最多也不行啊。还是例1,如果取个子解为1,2,3一起运,也会导致整体运送次数增多
酒逍遥
酒逍遥
回复 @wsg : 好像也不行..
酒逍遥
酒逍遥
回复 @wsg : 确实, 子解不成立. 那么子解为每次运送最多数量的石头呢?
wsg
wsg
上面的例1,如果取得某个子解为8和9一起运。虽然这个子解本身是最优,但是他导致整体运送次数至少多了一次。
0
子矜
子矜
以贫道看来,将所有方法进行排列组合,写入到数据库中,然后select出次数最小的,绝对是最优解
wsg
wsg
回复 @wsg : 当然,这个如果能够等到结果,那肯定是最优解
wsg
wsg
这个太暴力,所有方法写出来的话,我的机器会累死,我也会等结果等到死的。
0
L5_Railgun
L5_Railgun
只要保证在 质量 < w的情况下,尽可能多的数量个石头,就肯定是最优解了
L5_Railgun
L5_Railgun
回复 @wsg : 哦,我看走眼了,还有数量限制啊
wsg
wsg
这样不一定啊。 比如上面的例1,如果取个子解为1,2,3一起运,也会导致整体运送次数增多
0
Grrrr
Grrrr
我给你介绍个高人来解决. @expl0rer
random_walk
random_walk
回复 @wsg : 我被高估了,(^o^),我也不会
wsg
wsg
O(∩_∩)O谢谢 @expl0rer 来帮帮忙吧
0
酒逍遥
酒逍遥
这是个 数学问题.
0
小竹子哥
小竹子哥

例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优先去掉最轻的


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


wsg
wsg
虽然还没有最终验证,但是感觉这个方法挺不错!O(∩_∩)O谢谢
返回顶部
顶部