w*****n
发帖数: 375 | 1 100件价格不同的古董放进10个排好序的箱子，每个箱子放10件。你按顺序打开箱子。
每打开一个新箱子，你可以拿起一件或多件古董，或者什么都不拿。 拿起的东西不能
放下，也不可以回头从已经打开的箱子里拿东西。打开第n个箱子后，就不能从第1到第n-1
个箱子拿东西。等全部箱子都打开时，你最多手里可
以有10件古董。问怎样操作可以期望你最后手上的东西的总价格最高？ |
s*****n
发帖数: 2174 | 2 这个问题本身不make sense， 肯定什么地方表述错了。
否则看到价值最高的十件古董就拿， 否则就不拿。
那样就肯定可以确保最后拿到的东西总价最高了。 |
w*****n
发帖数: 375 | 3 不可以回头从已经打开的箱子里拿东西. 打开第n个箱子，就不能从第1，。。， 第n-1
个箱子拿东西。
【在 s*****n 的大作中提到】
: 这个问题本身不make sense， 肯定什么地方表述错了。
: 否则看到价值最高的十件古董就拿， 否则就不拿。
: 那样就肯定可以确保最后拿到的东西总价最高了。
|
s*****n
发帖数: 2174 | 4 我知道， 比如说100件古董的价值分别为A1
那么我从第一个箱子开始打开， 遇上A91－A100我就拿， 否则就不拿。
那么拿到最后， 可以确保拿到A91－A100啊， 不用回头拿以前箱子里的东西。
-1
【在 w*****n 的大作中提到】
: 不可以回头从已经打开的箱子里拿东西. 打开第n个箱子，就不能从第1，。。， 第n-1
: 个箱子拿东西。
|
w*****n
发帖数: 375 | 5 你打开第一个箱子的时候，不知道后面箱子里的东西的价格。
【在 s*****n 的大作中提到】
: 我知道， 比如说100件古董的价值分别为A1: 那么我从第一个箱子开始打开， 遇上A91－A100我就拿， 否则就不拿。
: 那么拿到最后， 可以确保拿到A91－A100啊， 不用回头拿以前箱子里的东西。
:
: -1
|
s*****n
发帖数: 2174 | 6 那样的话不可能存在某种办法能够确保总价值最高啊。
故计是问什么办法能使总价值的期望最大。
【在 w*****n 的大作中提到】
: 你打开第一个箱子的时候，不知道后面箱子里的东西的价格。
|
k*****u
发帖数: 1688 | 7 价格是明白的么？是的话，打开箱子，有91～100的就拿，没有就不拿 |
k*****u
发帖数: 1688 | 8 后面每个箱子里的价格都不知道，感觉应该打开每个箱子，把最高价格拿走。
好像要用到抽屉原理和均匀分布
做这些问题还是挺有意思的。偶昨天做这些问题赢了个奖品 哈哈 |
s*********r
发帖数: 909 | 9 应该是还没有打开的箱子里的价格是不明白的，不然没什么意思。
【在 k*****u 的大作中提到】
: 价格是明白的么？是的话，打开箱子，有91～100的就拿，没有就不拿
|
s*****n
发帖数: 2174 | 10 如果strategy必须提前定好， 那么：
根据最大似然原则， 最大的10个顺序统计量是均匀分布。
每个箱子会分到一个， 肯定是每个箱子里面选最大的。
严格证明估计并不容易， 结论倒是直观。
如果strategy并不一定提前定好， 而是可以随机应变， 那么直观上， 可能存在更好
的办法。
比如说第一个箱子， 由于10件古董是100件古董里面的”均匀“分布， 可以提供整体
100件古董价值的range信息。 这些信息， 可能对后面的箱子有指导作用。 如果第m个
箱子里面的最大值， 低于前面总体的某个quantile就不拿， 如果第m个箱子里面的几
个物品都超过前面总体的某个quantile， 就拿多个。 这个感觉就成了动态规划的问题
了。
【在 k*****u 的大作中提到】
: 后面每个箱子里的价格都不知道，感觉应该打开每个箱子，把最高价格拿走。
: 好像要用到抽屉原理和均匀分布
: 做这些问题还是挺有意思的。偶昨天做这些问题赢了个奖品 哈哈
|
|
|
k*****u
发帖数: 1688 | 11 那个“随机应变”好像不行啊。
我开始也觉得应该比较后面箱子跟前面箱子的max，或者前几个max。但是发现好像不行
。要是大数都在前面，你后面就拿不到了。是不是？
所以每个箱子拿最大的，不能保证你拿到最高的10个价格。但是反复拿的话，总体应该
效果最好
【在 s*****n 的大作中提到】
: 如果strategy必须提前定好， 那么：
: 根据最大似然原则， 最大的10个顺序统计量是均匀分布。
: 每个箱子会分到一个， 肯定是每个箱子里面选最大的。
: 严格证明估计并不容易， 结论倒是直观。
: 如果strategy并不一定提前定好， 而是可以随机应变， 那么直观上， 可能存在更好
: 的办法。
: 比如说第一个箱子， 由于10件古董是100件古董里面的”均匀“分布， 可以提供整体
: 100件古董价值的range信息。 这些信息， 可能对后面的箱子有指导作用。 如果第m个
: 箱子里面的最大值， 低于前面总体的某个quantile就不拿， 如果第m个箱子里面的几
: 个物品都超过前面总体的某个quantile， 就拿多个。 这个感觉就成了动态规划的问题
|
k*****u
发帖数: 1688 | 12 其实应该问问，当年上小学时，那个猴子怎么拿苞米的 |
s*****n
发帖数: 2174 | 13 这个是个概率问题， 在大数都在前面这种extreme cases下，当然performance不会好
。问题在于这种情况发生的概率及整体价值的expectation。就像你说的反复拿的话，
总体结果如何要仔细计算才行。 即使每个箱子里面拿最大的， 也照样在extreme case
情况下效果不好， 比如10个最大value都集中于一个箱子里面。
至于拿不到的情况不会出现。 这种strategy肯定是已经拿了n个， 还剩m个箱子， 以
及一些前面样本的统计量的函数 F（m，n， something else）。 最后拿满是肯定的，
价值多少不好说。 感觉这是个动态规划问题， 有点像背包问题。
【在 k*****u 的大作中提到】
: 那个“随机应变”好像不行啊。
: 我开始也觉得应该比较后面箱子跟前面箱子的max，或者前几个max。但是发现好像不行
: 。要是大数都在前面，你后面就拿不到了。是不是？
: 所以每个箱子拿最大的，不能保证你拿到最高的10个价格。但是反复拿的话，总体应该
: 效果最好
|
s*****n
发帖数: 2174 | 14 这问题还挺有意思， 写了几行程序simulate了一下。
（1） 每个箱子里面取最大的， 这个的理论依据是最大似然分布。
（2） 第一个箱子里面取最大的， 以后的箱子里面取超过现有平均值90%的， 直到取
满10个为止。 不足的话最后一个箱子补齐。 这个strategy就是基于动态规划的思想，
当然这是个非常简化的情况。
结果是
（1）的期望更大
（2）比（1）高的概率大约60%。
也就是说大约有60%的可能（2）比（1）好， 但是好的都不多。 偶尔（2）比（1）差
， 而且差很多。 |
g********r
发帖数: 8017 | 15 看起来象那个股票投资技巧有关。就是每星期买固定量的。
如果每个巷子对后面没有预测价值，就取最大一个好了。 |
s*****n
发帖数: 2174 | 16 问题就在于前面的箱子对后面是有预测价值的.
【在 g********r 的大作中提到】
: 看起来象那个股票投资技巧有关。就是每星期买固定量的。
: 如果每个巷子对后面没有预测价值，就取最大一个好了。
|
n*2
发帖数: 19062 | 17 问题就在于前面的箱子对后面是有预测价值的.
嗯，难点就是在这吧 |
l*******g
发帖数: 28 | 18 这个题目不那么简单，似乎是某年（九几年吧）的国际数学奥林匹克竞赛题的改编 |
f*********g
发帖数: 79 | 19 这个问题可能要用随机过程
网上看到过一个关于女生选择老公的搞笑paper，但是和这个很类似，不过是简化版本
的。
就是说女生很有很多追求者，但是如何选择是一个问题，因为永远不知道将来的怎样。
那个paper用了随机过程还有其它方法，最后算出来的最优结果是：
如果女生估计总共会遇到n个追求者，那么前n/e(e是自然对数）个追求者无论怎样一律
拒绝，后面的只要比之前的好就接受。
我觉得这两个很像，只不过允许一妻多夫，而且相亲的时候还是群面～，然后看看怎么
让老公们加起来比较强～ |
a******n
发帖数: 11246 | 20
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~关键是怎么摆的。对于不同的价值分布，
策略是不同的。所以如果你不知道摆放方法，没有一个策略能beat所有别的。
第n-1
【在 w*****n 的大作中提到】
: 100件价格不同的古董放进10个排好序的箱子，每个箱子放10件。你按顺序打开箱子。
: 每打开一个新箱子，你可以拿起一件或多件古董，或者什么都不拿。 拿起的东西不能
: 放下，也不可以回头从已经打开的箱子里拿东西。打开第n个箱子后，就不能从第1到第n-1
: 个箱子拿东西。等全部箱子都打开时，你最多手里可
: 以有10件古董。问怎样操作可以期望你最后手上的东西的总价格最高？
|
