S*******g
发帖数: 385 | 1 一个人要从A地去B地，之间的距离1000米。
该人有3000块饼干想从A地带到B地，但是一次最多可以携带1000块饼干。
但该鸟人每走一米要吃一块饼干。
问：可以从A地到B地携带饼干的最大数量是多少？
让当场设计一个Excel Macro去解决上面这个问题，可以用in-cell parameters
(so the count, distance, and capacity parameters can be changed）。
没答上来，胡诌了一通，当时自己感觉相当不好。。。。哭～～～～～
大侠们给讲讲呗～～～ |
x**y
发帖数: 10012 | 2 那个汽车运油问题的改进版么....
【在 S*******g 的大作中提到】
: 一个人要从A地去B地，之间的距离1000米。
: 该人有3000块饼干想从A地带到B地，但是一次最多可以携带1000块饼干。
: 但该鸟人每走一米要吃一块饼干。
: 问：可以从A地到B地携带饼干的最大数量是多少？
: 让当场设计一个Excel Macro去解决上面这个问题，可以用in-cell parameters
: (so the count, distance, and capacity parameters can be changed）。
: 没答上来，胡诌了一通，当时自己感觉相当不好。。。。哭～～～～～
: 大侠们给讲讲呗～～～
|
V**0
发帖数: 889 | 3 这有解吗？
一次最多带1000块，单程就得吃1000块饼干，走到刚好吃完，回不来了啊
还是我题意理解错了？
【在 S*******g 的大作中提到】
: 一个人要从A地去B地，之间的距离1000米。
: 该人有3000块饼干想从A地带到B地，但是一次最多可以携带1000块饼干。
: 但该鸟人每走一米要吃一块饼干。
: 问：可以从A地到B地携带饼干的最大数量是多少？
: 让当场设计一个Excel Macro去解决上面这个问题，可以用in-cell parameters
: (so the count, distance, and capacity parameters can be changed）。
: 没答上来，胡诌了一通，当时自己感觉相当不好。。。。哭～～～～～
: 大侠们给讲讲呗～～～
|
x**y
发帖数: 10012 | 4 带三次 到2/3的地方卸下来
最后凑1000走最后1/3
【在 V**0 的大作中提到】
: 这有解吗？
: 一次最多带1000块，单程就得吃1000块饼干，走到刚好吃完，回不来了啊
: 还是我题意理解错了？
|
S*******g
发帖数: 385 | 5 我也是这个思路于是僵在那里了.....555555~~~~~
xmly大虾你给个汽车运油问题的链接看看呗～～～
多谢啦～
【在 V**0 的大作中提到】
: 这有解吗？
: 一次最多带1000块，单程就得吃1000块饼干，走到刚好吃完，回不来了啊
: 还是我题意理解错了？
|
x**y
发帖数: 10012 | 6 给你答案了
【在 S*******g 的大作中提到】
: 我也是这个思路于是僵在那里了.....555555~~~~~
: xmly大虾你给个汽车运油问题的链接看看呗～～～
: 多谢啦～
|
S*******g
发帖数: 385 | 7 带到2/3处后，难道回程不需要走一米吃块饼干吗？
【在 x**y 的大作中提到】
: 带三次 到2/3的地方卸下来
: 最后凑1000走最后1/3
|
h*y
发帖数: 1289 | 8 好像最早的版本是骆驼吧
【在 x**y 的大作中提到】
: 那个汽车运油问题的改进版么....
|
x**y
发帖数: 10012 | 9 哦
对
反正思路就是你要算最后一次能凑齐1000的某个地方
者必须就是最大的了
【在 S*******g 的大作中提到】
: 带到2/3处后，难道回程不需要走一米吃块饼干吗？
|
x**y
发帖数: 10012 | 10 骆驼镇可恶...
【在 h*y 的大作中提到】
: 好像最早的版本是骆驼吧
|
|
|
V**0
发帖数: 889 | 11 动态规划？
F(m, n) = min {2*x*(n/1000)+F(m-x,n-2*x*(n/1000))}
m=1000, n=3000 初值
【在 x**y 的大作中提到】
: 带三次 到2/3的地方卸下来
: 最后凑1000走最后1/3
|
x**y
发帖数: 10012 | 12 跟dp没什么关系吧
最优解有且只有一个 就是最后一趟得凑齐1000
而且是越近越好
【在 V**0 的大作中提到】
: 动态规划？
: F(m, n) = min {2*x*(n/1000)+F(m-x,n-2*x*(n/1000))}
: m=1000, n=3000 初值
|
S*******g
发帖数: 385 | 13 第一次1000块：运到1/4处消耗250块，卸下来500块，载着剩下的250块回程
第二次1000块：运到1/4处消耗250块后，从第一次卸下来的500块中拿250块继续走到1/
2处，这时卸载250块，驮着剩余的500块返程
第三次1000块：运到运到1/4处消耗250块，从第一次卸下来的500块中拿剩下的250块继
续走到1/2处，拿第二次卸下来的250块，现在总数1000块走最后的500米。
所以最后的结果是500块饼干。。。
这样思路对吗? |
x**y
发帖数: 10012 | 14 (1000-2x)+(1000-2x)+(1000-x) = 1000
x =400
final = 1000 - 400 = 600
1/
【在 S*******g 的大作中提到】
: 第一次1000块：运到1/4处消耗250块，卸下来500块，载着剩下的250块回程
: 第二次1000块：运到1/4处消耗250块后，从第一次卸下来的500块中拿250块继续走到1/
: 2处，这时卸载250块，驮着剩余的500块返程
: 第三次1000块：运到运到1/4处消耗250块，从第一次卸下来的500块中拿剩下的250块继
: 续走到1/2处，拿第二次卸下来的250块，现在总数1000块走最后的500米。
: 所以最后的结果是500块饼干。。。
: 这样思路对吗?
|
V**0
发帖数: 889 | 15 感觉是一个dp的问题：第一步把3000个通过几个来回搬到一个中间点，然后又问题变成
了与原问题类似的一个问题，只是比1000米少（因为在中间点），没有3000个（因为来
回几趟要吃饼干）。
关键就是中间点的选取，使得运到终点时总共吃掉的饼干最少，这样就搬运最大量的饼
干过去了。由于不止一个中间点，每段多长，有几段都不清楚，所以动态规划来找吧
【在 x**y 的大作中提到】
: 跟dp没什么关系吧
: 最优解有且只有一个 就是最后一趟得凑齐1000
: 而且是越近越好
|
x**y
发帖数: 10012 | 16 恩
也可以这么想
你说的是对的
【在 V**0 的大作中提到】
: 感觉是一个dp的问题：第一步把3000个通过几个来回搬到一个中间点，然后又问题变成
: 了与原问题类似的一个问题，只是比1000米少（因为在中间点），没有3000个（因为来
: 回几趟要吃饼干）。
: 关键就是中间点的选取，使得运到终点时总共吃掉的饼干最少，这样就搬运最大量的饼
: 干过去了。由于不止一个中间点，每段多长，有几段都不清楚，所以动态规划来找吧
|
V**0
发帖数: 889 | 17 这是面Quant的问题么...不是Quant应该问很多stochastic的吗？
【在 S*******g 的大作中提到】
: 一个人要从A地去B地，之间的距离1000米。
: 该人有3000块饼干想从A地带到B地，但是一次最多可以携带1000块饼干。
: 但该鸟人每走一米要吃一块饼干。
: 问：可以从A地到B地携带饼干的最大数量是多少？
: 让当场设计一个Excel Macro去解决上面这个问题，可以用in-cell parameters
: (so the count, distance, and capacity parameters can be changed）。
: 没答上来，胡诌了一通，当时自己感觉相当不好。。。。哭～～～～～
: 大侠们给讲讲呗～～～
|
S*******g
发帖数: 385 | 18 这个400是指在400米处卸货，最终在这个400米处凑足1000块
还剩下600米的路，那么最后到B地只剩下400块了。比刚才那个1/4,1/2卸货装货还少
100块。。。。
感觉上可以在不同地方卸货，不一定非要找一个点卸下来。对不？
DP的我再好好顺着这个思路想想～～～
【在 x**y 的大作中提到】
: (1000-2x)+(1000-2x)+(1000-x) = 1000
: x =400
: final = 1000 - 400 = 600
:
: 1/
|
S*******g
发帖数: 385 | 19 Quantitative Analyst
感觉面试问题千奇百怪的，问啥的都可能有滴～～～
这个感觉就是考人的分析解决问题能力吧
【在 V**0 的大作中提到】
: 这是面Quant的问题么...不是Quant应该问很多stochastic的吗？
|
x**y
发帖数: 10012 | 20 结果问来问去都是老题目
顶多汽车改鸟人 骆驼换汽车
可见问人的这帮人也不怎么样
【在 S*******g 的大作中提到】
: Quantitative Analyst
: 感觉面试问题千奇百怪的，问啥的都可能有滴～～～
: 这个感觉就是考人的分析解决问题能力吧
|
|
|
d**********9
发帖数: 5215 | 21 I think your final answer missed the amount of crackers that will be
consumed from the last place you assemble 1000 crackers to the final
destination. The result should be less than 600.
【在 x**y 的大作中提到】
: (1000-2x)+(1000-2x)+(1000-x) = 1000
: x =400
: final = 1000 - 400 = 600
:
: 1/
|
x**y
发帖数: 10012 | 22 哦
对
1000-600
搞错了
【在 d**********9 的大作中提到】
: I think your final answer missed the amount of crackers that will be
: consumed from the last place you assemble 1000 crackers to the final
: destination. The result should be less than 600.
|
x**y
发帖数: 10012 | 23 你说的对
这个问题可以不断缩距离和运货量
我觉得bottom up 似乎更简单?
【在 S*******g 的大作中提到】
: 这个400是指在400米处卸货，最终在这个400米处凑足1000块
: 还剩下600米的路，那么最后到B地只剩下400块了。比刚才那个1/4,1/2卸货装货还少
: 100块。。。。
: 感觉上可以在不同地方卸货，不一定非要找一个点卸下来。对不？
: DP的我再好好顺着这个思路想想～～～
|
G*****u
发帖数: 1222 | 24 写了个macro来算
最多能带400个cookie
另外我还弄了个spreadsheet来算 你想要的话可以给我发站内信
这个好像不能上传excel文件
Sub MaxCookie()
Dim Balance(1 To 1000), FirstTrip(1 To 1000), SecondTrip(1 To 1000),
FinalBalance(1 To 1000) As Variant
Dim i As Integer
Balance(1) = 999
For i = 2 To 1000
Balance(i) = Balance(i - 1) - 1
Next i
For i = 1 To 1000
If Balance(i) - 1 < 0 Then
FirstTrip(i) = 0
Else
FirstTrip(i) = Balance(i) - i
End If
Next i
For i = 1 To 1000
If Application.WorksheetFunction.Min(Balance(i) + FirstTrip(i), 1000) - i <
0 Then
【在 S*******g 的大作中提到】
: 一个人要从A地去B地，之间的距离1000米。
: 该人有3000块饼干想从A地带到B地，但是一次最多可以携带1000块饼干。
: 但该鸟人每走一米要吃一块饼干。
: 问：可以从A地到B地携带饼干的最大数量是多少？
: 让当场设计一个Excel Macro去解决上面这个问题，可以用in-cell parameters
: (so the count, distance, and capacity parameters can be changed）。
: 没答上来，胡诌了一通，当时自己感觉相当不好。。。。哭～～～～～
: 大侠们给讲讲呗～～～
|
S*******g
发帖数: 385 | 25 Gaminyu大虾，就是这个～～～
第一次1000块：运到1/4处消耗250块，卸下来500块，载着剩下的250块回程
第二次1000块：运到1/4处消耗250块后，从第一次卸下来的500块中拿250块继续走到1/
2处，这时卸载250块，驮着剩余的500块返程
第三次1000块：运到运到1/4处消耗250块，从第一次卸下来的500块中拿剩下的250块继
续走到1/2处，拿第二次卸下来的250块，现在总数1000块走最后的500米。
所以最后的结果是500块饼干。。。
这样思路对吗?
【在 G*****u 的大作中提到】
: 写了个macro来算
: 最多能带400个cookie
: 另外我还弄了个spreadsheet来算 你想要的话可以给我发站内信
: 这个好像不能上传excel文件
: Sub MaxCookie()
: Dim Balance(1 To 1000), FirstTrip(1 To 1000), SecondTrip(1 To 1000),
: FinalBalance(1 To 1000) As Variant
: Dim i As Integer
: Balance(1) = 999
: For i = 2 To 1000
|
x**y
发帖数: 10012 | 26 没看出什么不对．．．
其实你都可以沿途一mile扔一块．．．．
1/
【在 S*******g 的大作中提到】
: Gaminyu大虾，就是这个～～～
: 第一次1000块：运到1/4处消耗250块，卸下来500块，载着剩下的250块回程
: 第二次1000块：运到1/4处消耗250块后，从第一次卸下来的500块中拿250块继续走到1/
: 2处，这时卸载250块，驮着剩余的500块返程
: 第三次1000块：运到运到1/4处消耗250块，从第一次卸下来的500块中拿剩下的250块继
: 续走到1/2处，拿第二次卸下来的250块，现在总数1000块走最后的500米。
: 所以最后的结果是500块饼干。。。
: 这样思路对吗?
|
i*****r
发帖数: 1302 | |
G*****u
发帖数: 1222 | 28 不好意思 我刚刚弄错了些东西
我原来的假定第一次和第二次trip只能卸载一次，最后一次trip只能补装一次原来卸载
下的cookie
我又写了一个code
现在的设定是第一次和第二次trip只能卸载一次，最后一次trip能补装两次前两个trip
卸下来的cookie
算出来的数字是444
还没想到怎样才能做到前两次可以随意卸载，最后一次能随意补装
你可以试着建个1000*1000的matrix算算
Sub MaxCookieV2()
Dim Balance(1 To 1000), UnloadBalance(1 To 1000), FinalBalance(1 To 1000) As
Variant
Dim FirstSupply(), SecondSupply(), EndBalance() As Variant
Dim i, j As Integer
''' Balance of Each Trip with Starting Balance 1000
Balance(1) = 999
Cells(1, 4) = Balance(1)
For i = 2 To 1000
Balan
【在 S*******g 的大作中提到】
: Gaminyu大虾，就是这个～～～
: 第一次1000块：运到1/4处消耗250块，卸下来500块，载着剩下的250块回程
: 第二次1000块：运到1/4处消耗250块后，从第一次卸下来的500块中拿250块继续走到1/
: 2处，这时卸载250块，驮着剩余的500块返程
: 第三次1000块：运到运到1/4处消耗250块，从第一次卸下来的500块中拿剩下的250块继
: 续走到1/2处，拿第二次卸下来的250块，现在总数1000块走最后的500米。
: 所以最后的结果是500块饼干。。。
: 这样思路对吗?
|
k*******d
发帖数: 1340 | 29 我觉得Sirrening的500块比xmly的400块优，问题是，还有没有更优的，Sirrening，你
是怎么想到这个思路的？有没有systematic的思路？ |
S*******g
发帖数: 385 | 30 Gaminyu, 你是最最最可爱的人～～～
散花狂赞哦～～～
我用方程求的解：
第一次途中在X1处卸载一次，卸载量1000－2*X1
第二次走到X1处把1000填满，然后走到X2处卸载,留购回程的就成（卸载量1000－（X2-
X1）-X2），
第三次走到X1处把1000填满，走到X2处继续填满1000，剩下的就边走边吃直到B处
这样做，其实就是要在第三次运输过程中，第一次填满1000的时侯X1处剩余刚好是0（
也就意味着X1处剩余的刚好把1000填满），第二次填满1000的时侯X2处剩余刚好是0(意
味着在X2处可以重新填满成1000). 只针对第三次trip的填满车的量，这样就可以列出
如下方程：
1000－2*X1-X1+(1000-X1)=1000
1000-(X2-X1)-X2+1000-(X2-X1)=1000
解出来：X1=250
X2=500
跟我前面山寨那个猜测答案刚好相符。
这样对吗？我就能想到这个了～～～
trip
【在 G*****u 的大作中提到】
: 不好意思 我刚刚弄错了些东西
: 我原来的假定第一次和第二次trip只能卸载一次，最后一次trip只能补装一次原来卸载
: 下的cookie
: 我又写了一个code
: 现在的设定是第一次和第二次trip只能卸载一次，最后一次trip能补装两次前两个trip
: 卸下来的cookie
: 算出来的数字是444
: 还没想到怎样才能做到前两次可以随意卸载，最后一次能随意补装
: 你可以试着建个1000*1000的matrix算算
: Sub MaxCookieV2()
|
|
|
G*****u
发帖数: 1222 | 31 我刚刚想到一个小trick在macro实现你的想法
其实就是把第一次没有带走的饼干转嫁到第二次（在第二次trip里）
你自己看一下吧
Sub MaxCookieV3()
Dim Balance(1 To 1000), UnloadBalance(1 To 1000), FinalBalance(1 To 1000) As
Variant
Dim FirstSupply(), SecondSupply(), EndBalance() As Variant
Dim i, j As Integer
''' Balance of Each Trip with Starting Balance 1000
Balance(1) = 999
For i = 2 To 1000
Balance(i) = Balance(i - 1) - 1
Next i
''' Unload Process
For i = 1 To 1000
If (Balance(i) - i) < 0 Then
UnloadBalance(i) = 0
Else
UnloadBalance(i) = Balance(i) - i
【在 S*******g 的大作中提到】
: Gaminyu, 你是最最最可爱的人～～～
: 散花狂赞哦～～～
: 我用方程求的解：
: 第一次途中在X1处卸载一次，卸载量1000－2*X1
: 第二次走到X1处把1000填满，然后走到X2处卸载,留购回程的就成（卸载量1000－（X2-
: X1）-X2），
: 第三次走到X1处把1000填满，走到X2处继续填满1000，剩下的就边走边吃直到B处
: 这样做，其实就是要在第三次运输过程中，第一次填满1000的时侯X1处剩余刚好是0（
: 也就意味着X1处剩余的刚好把1000填满），第二次填满1000的时侯X2处剩余刚好是0(意
: 味着在X2处可以重新填满成1000). 只针对第三次trip的填满车的量，这样就可以列出
|
S*********g
发帖数: 5298 | 32 For the first 200m, each meter will cost 5 biscutes
For the next 1000/3m, each meter will cost 3 biscutes
for the remaining 1000 (1-1/3-1/5), each meter will cost 1 biscute
You can move 1000 (1/3+1/5) = 533.33 biscutes to the destination
【在 S*******g 的大作中提到】
: 一个人要从A地去B地，之间的距离1000米。
: 该人有3000块饼干想从A地带到B地，但是一次最多可以携带1000块饼干。
: 但该鸟人每走一米要吃一块饼干。
: 问：可以从A地到B地携带饼干的最大数量是多少？
: 让当场设计一个Excel Macro去解决上面这个问题，可以用in-cell parameters
: (so the count, distance, and capacity parameters can be changed）。
: 没答上来，胡诌了一通，当时自己感觉相当不好。。。。哭～～～～～
: 大侠们给讲讲呗～～～
|
x**y
发帖数: 10012 | 33 correct
niub
【在 S*********g 的大作中提到】
: For the first 200m, each meter will cost 5 biscutes
: For the next 1000/3m, each meter will cost 3 biscutes
: for the remaining 1000 (1-1/3-1/5), each meter will cost 1 biscute
: You can move 1000 (1/3+1/5) = 533.33 biscutes to the destination
|
S*******g
发帖数: 385 | 34 芝麻他爹，给展开讲讲吧，芝麻他姐看不懂啊～～～ blush.....
【在 S*********g 的大作中提到】
: For the first 200m, each meter will cost 5 biscutes
: For the next 1000/3m, each meter will cost 3 biscutes
: for the remaining 1000 (1-1/3-1/5), each meter will cost 1 biscute
: You can move 1000 (1/3+1/5) = 533.33 biscutes to the destination
|
S*********g
发帖数: 5298 | 35 To move all cookies one meter forward starting from the origin, the birdman
will have to run at least 3 times (or 2.5 round trips because he does not
need to come back for the last run). This will cost 5 cookies. This is so
till 1000 cookies are consumed. Now, to move 1 meter forward, he will need
to run at least 2 times (1.5 round trips) which costs 3 cookies. After the
2nd 1000 cookie are consumed, he can just run towards the endline without
looking back.
【在 S*******g 的大作中提到】
: 芝麻他爹，给展开讲讲吧，芝麻他姐看不懂啊～～～ blush.....
|
p********2
发帖数: 9939 | 36 棒
birdman
【在 S*********g 的大作中提到】
: To move all cookies one meter forward starting from the origin, the birdman
: will have to run at least 3 times (or 2.5 round trips because he does not
: need to come back for the last run). This will cost 5 cookies. This is so
: till 1000 cookies are consumed. Now, to move 1 meter forward, he will need
: to run at least 2 times (1.5 round trips) which costs 3 cookies. After the
: 2nd 1000 cookie are consumed, he can just run towards the endline without
: looking back.
|
p********2
发帖数: 9939 | 37 再问，如果那个cookie数不是整数呢？比如1100颗等等。有没有generalized的公式可
以解答呢？
birdman
【在 S*********g 的大作中提到】
: To move all cookies one meter forward starting from the origin, the birdman
: will have to run at least 3 times (or 2.5 round trips because he does not
: need to come back for the last run). This will cost 5 cookies. This is so
: till 1000 cookies are consumed. Now, to move 1 meter forward, he will need
: to run at least 2 times (1.5 round trips) which costs 3 cookies. After the
: 2nd 1000 cookie are consumed, he can just run towards the endline without
: looking back.
|
S*******g
发帖数: 385 | 38 我真的很笨，还是没看懂。。5555～～～
不是在某一点卸货，然后回程，第二次路过的时侯再填满吗？
前面芝麻他爹的solution: 200m, 1000/3 m是指两个卸货点？
如果是，第二次经过200m点的时候，只能从上次卸货的600个里面带走200个对吗？第三
次经过200m点的时侯同样带走200个，那么200米处还剩200个啊？
芝麻他爹对不住，能不能再仔细讲讲，太感谢了～！
birdman
【在 S*********g 的大作中提到】
: To move all cookies one meter forward starting from the origin, the birdman
: will have to run at least 3 times (or 2.5 round trips because he does not
: need to come back for the last run). This will cost 5 cookies. This is so
: till 1000 cookies are consumed. Now, to move 1 meter forward, he will need
: to run at least 2 times (1.5 round trips) which costs 3 cookies. After the
: 2nd 1000 cookie are consumed, he can just run towards the endline without
: looking back.
|
p********2
发帖数: 9939 | 39 我来写一下偶的理解。
最主要的就是每往前走1m就要带尽量多的cookie。所以最优解是每次挪一米，带1000块
cookie，然后回来再带1000块cookie以此类推。
但是有一点是不是要注意一下，如果是1001 或者1002颗cookie了，那么最后的一趟就
不要挪了。
【在 S*******g 的大作中提到】
: 我真的很笨，还是没看懂。。5555～～～
: 不是在某一点卸货，然后回程，第二次路过的时侯再填满吗？
: 前面芝麻他爹的solution: 200m, 1000/3 m是指两个卸货点？
: 如果是，第二次经过200m点的时候，只能从上次卸货的600个里面带走200个对吗？第三
: 次经过200m点的时侯同样带走200个，那么200米处还剩200个啊？
: 芝麻他爹对不住，能不能再仔细讲讲，太感谢了～！
:
: birdman
|
d**********9
发帖数: 5215 | 40 the second unload location is 200+1000/3
【在 S*******g 的大作中提到】
: 我真的很笨，还是没看懂。。5555～～～
: 不是在某一点卸货，然后回程，第二次路过的时侯再填满吗？
: 前面芝麻他爹的solution: 200m, 1000/3 m是指两个卸货点？
: 如果是，第二次经过200m点的时候，只能从上次卸货的600个里面带走200个对吗？第三
: 次经过200m点的时侯同样带走200个，那么200米处还剩200个啊？
: 芝麻他爹对不住，能不能再仔细讲讲，太感谢了～！
:
: birdman
|
|
|
p********2
发帖数: 9939 | 41 我觉得还是一米一米挪比较好理解，in case，cookie数不是1000的倍数的时候。
【在 d**********9 的大作中提到】
: the second unload location is 200+1000/3
|
z****e
发帖数: 2024 | 42 感觉申请金融工作的话，答对题目与否并不很重要。看顺眼很重要。
因为申请人多了，所以就乱问，其实工作要求并不太高。
【在 x**y 的大作中提到】
: 结果问来问去都是老题目
: 顶多汽车改鸟人 骆驼换汽车
: 可见问人的这帮人也不怎么样
|
S*********g
发帖数: 5298 | 43 yes, what you said is one of the most straightforward solutions.
There are many more equivalent solutions. The point is for first 200m, the
man will have to run 3 times and he will have to move all the cookies to
200m mark. Then move all the cookies to 200 + 1000/3 with 2 runs
Another solution is
1. load 1000 at the origin, unload 600 at 200m, come back
2. load 1000 at the origin, unload 600 at 200m, come back
3. load 1000 at the origin, at 200m pick 200 cookies (1000 cookies left at
200m), unlo
【在 p********2 的大作中提到】
: 我觉得还是一米一米挪比较好理解，in case，cookie数不是1000的倍数的时候。
|
S*********g
发帖数: 5298 | 44 see 22396
【在 S*******g 的大作中提到】
: 我真的很笨，还是没看懂。。5555～～～
: 不是在某一点卸货，然后回程，第二次路过的时侯再填满吗？
: 前面芝麻他爹的solution: 200m, 1000/3 m是指两个卸货点？
: 如果是，第二次经过200m点的时候，只能从上次卸货的600个里面带走200个对吗？第三
: 次经过200m点的时侯同样带走200个，那么200米处还剩200个啊？
: 芝麻他爹对不住，能不能再仔细讲讲，太感谢了～！
:
: birdman
|
f*******y
发帖数: 988 | 45 正解中的正解
brain teaser基本是瞎扯淡
【在 z****e 的大作中提到】
: 感觉申请金融工作的话，答对题目与否并不很重要。看顺眼很重要。
: 因为申请人多了，所以就乱问，其实工作要求并不太高。
|
S*******g
发帖数: 385 | 46 芝麻他爹 多谢多谢～！
到底是爹地级别的人物！赞～！！ ^-^
【在 S*********g 的大作中提到】
: see 22396
|
S*******g
发帖数: 385 | 47 我觉得general solution是：
需要中间卸载的次数：3000/1000-1=2
这意味着在A点到第一个卸载点之间，每米消耗3*2-1=5个cookie
第一个卸载点到第二个卸载点之间，每米消耗2*2-1=3个cookie
第一个unload点位于：1000/5=200m处
第二个unload点位于：1000/3+200 m 处
更general 说：
unload/upload points on the way: (Count/Capacity)-1=Consume 1
Cookie consumed between origin to unload point 1: (count/capacity)*2-1
Cookie consumed between unload point 1 to unload point 2: ((count/capacity)-
1)*2-1=consume2
............and so on...
The first unload point: capacity/consume1
The second unload |
k*******d
发帖数: 1340 | 48 希望真的不很重要啊， BT真BT。。。
我觉得专业知识类题目正确与否那还是比较重要的
剩下的就是运气也很重要了
【在 z****e 的大作中提到】
: 感觉申请金融工作的话，答对题目与否并不很重要。看顺眼很重要。
: 因为申请人多了，所以就乱问，其实工作要求并不太高。
|
a****j
发帖数: 1277 | |
p*****k
发帖数: 318 | |
|
|
d**********9
发帖数: 5215 | 51 thanks for sharing
【在 p*****k 的大作中提到】
: couple of variants have been discussed on this board/wilmott
: before. see e.g.,
: http://wilmott.com/messageview.cfm?catid=26&threadid=77062
: or,
: http://en.wikipedia.org/wiki/Jeep_problem
|
h*******u
发帖数: 15326 | 52 错了。100的时候剩600米。所以是1000-600=400 不是最优
【在 x**y 的大作中提到】
: correct
: niub
|
h*******u
发帖数: 15326 | 53 对
【在 S*********g 的大作中提到】
: For the first 200m, each meter will cost 5 biscutes
: For the next 1000/3m, each meter will cost 3 biscutes
: for the remaining 1000 (1-1/3-1/5), each meter will cost 1 biscute
: You can move 1000 (1/3+1/5) = 533.33 biscutes to the destination
|
z*****y
发帖数: 147 | 54 补充下牛人们的东西。如果限定饼干不能吃半块，不能走半米之类的，可能还要有修
正。
另外这个问题本质上还是dynamical programming或者过于简单的optimal control的问题
如果设定剩下的reward是R(x)（饼干数），move的cost （最少消耗多少饼干才能运到
下一格）是f(R), 比如饼干0-1000 f(R)=1, 1001-2000 f(R)=3, 2001-3000 f(R)=5
方程就是，
R(x)-R(x+1)>=f(R(x)),R(0)=3000， and maximize R(1000)
当然这是LP
已知R(0)=3000，没有道理不greedy(或者说linear programming的optimal solution永
远在boundary), R(x+1）=R(x)-f(R(x))，循环，对于任何load,任何终点，都能解出来。
这样结果是532。因为R总是在减少，得到一组R(x)的结果，总能复原出来到底怎么折返
。532的结果对应0-200往返2趟半, 200-534往返1趟半（R(534)=998），剩下就直接走
如果是连续
【在 p*****k 的大作中提到】
: couple of variants have been discussed on this board/wilmott
: before. see e.g.,
: http://wilmott.com/messageview.cfm?catid=26&threadid=77062
: or,
: http://en.wikipedia.org/wiki/Jeep_problem
|
b*********n
发帖数: 464 | 55 恩，我也是这么想的，不知道如果用每次移动的距离作为变量，求极限会不会结果更好。
【在 p********2 的大作中提到】
: 我来写一下偶的理解。
: 最主要的就是每往前走1m就要带尽量多的cookie。所以最优解是每次挪一米，带1000块
: cookie，然后回来再带1000块cookie以此类推。
: 但是有一点是不是要注意一下，如果是1001 或者1002颗cookie了，那么最后的一趟就
: 不要挪了。
|
f***e
发帖数: 43 | 56 533
饼干>2000，不管怎么搬，一次搬到200m处，还是一步一步的搬，
都得来回5次，消耗 5/m
3000-5x = 2000
x=200m
一旦<=2000,只需要消耗 3/m
2000-3x = 1000
x=333m
还剩下1001，扔下一块，带走1000块走剩下的 1000-200-333=467m
最后剩下 533块。 |
D******n
发帖数: 2836 | 57 I guess the real question is why is that solution optimal? these
solutions are all like they know they are right.....
【在 f*******y 的大作中提到】
: 正解中的正解
: brain teaser基本是瞎扯淡
|
f***e
发帖数: 43 | 58 证明optimal 实际上很简单，我只写了解法，懒得打字，当然可能有更elegent的方法
证明，我也懒得去想了。
let i=1,2,..., 1000
A_i, = {往前走 or 返回}
需要一下几个很显然的步骤，
1。 每次带最大限量的饼干往前，折回的话只带足够走回去的饼干数。
2。 每走一米，就有两种选择，继续向前，还是放下部分后返回，找到 optimal A_i
，就解决了问题。
3。 决定是向前还是返回，根据一个很简单的判定条件，如果要从 i 点返回，如果返
回后再回到 i 点，再次带来的饼干数 >0。
如此就得到了答案，再贴一遍。
533
饼干>2000，不管怎么搬，一次搬到200m处，还是一步一步的搬，
都得来回5次，消耗 5/m
3000-5x = 2000
x=200m
一旦<=2000,只需要消耗 3/m
2000-3x = 1000
x=333m
还剩下1001，扔下一块，带走1000块走剩下的 1000-200-333=467m
最后剩下 533块。 |
