a*******1
发帖数: 1554 | 1 5月1日星期五面的，我没做出来：
1个骆驼背3000条香蕉要走1000公里，它每走1公里要吃1根香蕉，一次最多背1000条。
问能够最多背多少过去？
谢谢！ |
l*********g
发帖数: 1899 | 2 这题属于“骆驼运香蕉，汽车运汽油，鸟人运饼干”类的问题。这个版多年前有详细讨
论过：
http://www.mitbbs.com/article_t1/Quant/31251495_0_1.html
【在 a*******1 的大作中提到】
: 5月1日星期五面的，我没做出来：
: 1个骆驼背3000条香蕉要走1000公里，它每走1公里要吃1根香蕉，一次最多背1000条。
: 问能够最多背多少过去？
: 谢谢！
|
a*******1
发帖数: 1554 | 3 谢谢！
【在 l*********g 的大作中提到】
: 这题属于“骆驼运香蕉，汽车运汽油，鸟人运饼干”类的问题。这个版多年前有详细讨
: 论过：
: http://www.mitbbs.com/article_t1/Quant/31251495_0_1.html
|
d********t
发帖数: 9628 | 4 考这种问题的地方其实根本没打算招人
【在 a*******1 的大作中提到】
: 5月1日星期五面的，我没做出来：
: 1个骆驼背3000条香蕉要走1000公里，它每走1公里要吃1根香蕉，一次最多背1000条。
: 问能够最多背多少过去？
: 谢谢！
|
p*********s
发帖数: 61 | 5 感觉是个动态规划的题目，估计有算法背景的同学也许可以做出来。
假设 f(distance, banana) 是背的次数，那么有如下关系（大概思路）：
1. if banana >1000:
f(distance, banana) = f(distance, 1000)
2. if banana >= distance and banana <= 1000:
f(distance, banana) = 1
3. otherwise:
f(distance, banana) = 1 + min [f(distance - y, 2*banana - 3*y)]
get the min by traversing all the valid y's
应该写个代码或者用excel可以算出来。大概思路如此，也许细节还需要修改。 |
c*****n
发帖数: 83 | 6 闲得无聊，回答一下这道题吧。
1. 分三次将 饼干运到 333.3 米处，得 3000 - 3 * 333.3 = 2000;
2. 分两次将 饼干从 333.3 米 运至 833.3 米处，得 2000 - 2 * 500 = 1000;
3. 最后一次 1000 - (1000 - 833.3) = 833.3
这是最优解 |
c*****n
发帖数: 83 | 7 关键思路：每个停留点所得必须是整千.
e.g. 若 3000 --> 3500, 则第一点是 125 米处。 |
p****e
发帖数: 3548 | 8 这个不对吧，走回去也得吃
【在 c*****n 的大作中提到】
: 闲得无聊，回答一下这道题吧。
: 1. 分三次将 饼干运到 333.3 米处，得 3000 - 3 * 333.3 = 2000;
: 2. 分两次将 饼干从 333.3 米 运至 833.3 米处，得 2000 - 2 * 500 = 1000;
: 3. 最后一次 1000 - (1000 - 833.3) = 833.3
: 这是最优解
|
c**e
发帖数: 4439 | 9 正确
【在 p****e 的大作中提到】
: 这个不对吧，走回去也得吃
|
G******n
发帖数: 572 | |
s*****w
发帖数: 1017 | 11 动态规划题
min(x1 + x2)
s.t.
x2 <= x1
1000 - 2 x1 >= 0;
1000 - 2 x2 >= 0;
3 x2 >= 1000
3 x1 + 2 x2 >= 2000
最后是一个解集是个梯形，拿斜率是-1的直线去截。得x1 = 444, x2 = 333.
剩1000-x1 = 555.56
不知道对不对 |
I***Y
发帖数: 33 | 12 第一次见到这题，感觉挺有趣的，趁洗澡的时候想了下。下面是我的思路，如有不对请
指出。
假设一开始要把香蕉都运到n米处，则这n米平均每米要消耗5根香蕉（去回去回去，共3
次）。剩下香蕉为3000-5n，当这个数大于2000的时候，不过n是多少，单位距离消耗的
香蕉都是一样多的。所以第一个stop 临界点应该是当n=200的时候。到这里后还剩2000
香蕉，下面假设第二部分前进m米，则这m米单位距离消耗香蕉数为3根，直到总剩余香
蕉数=1000为止，所以我们最远可以吧这些香蕉运送m= 1000/3=333米。所以应该停在
533米处。然后还剩1001根，拿上1000根走到底 还剩533根。这就是最大值。
现在讨论n是第一个最优点：假设第一次香蕉运送到大于200米处的地方，则剩余香蕉数
一定小雨2000并且递减速度为5根每米，大于后面运作的递减速度；另一方面，假设第
一次送到小于200米处，虽然剩余香蕉数多于2000，但为了运送超过2000根的部分，一
定需要来回第三次，所以对效率不会有所改进。最终还是只能运到200米处。
m为第二个最优点的讨论同理。
综上 最多可以运送533根。 |
I***Y
发帖数: 33 | 13 以上为假设香蕉是一根一吃的。如果香蕉被骆驼一1根每米的速度均匀连续的吃，则可
以打到533.333333...米 |
t****d
发帖数: 3204 | |
