每日一题 - 抽奖三选一

得同事所言：

在一次现场活动中，主持人请一位幸运观众上台抽奖，奖品是1000元钱，但是钱装在三个盒子中的某一个，然后主持人请这位幸运观众选择一个盒子，当然，这样选择的话只有1/3的机会拿到钱。然后主持人打开另外两个盒子中的一个，并证实它是空的，这是主持人问幸运观众：是否要选择另一个未打开的盒子？



==================== 上题分析 =====================
堆栈折叠问题分析

这一次的堆栈折叠问题可以对应到箱子装载问题，纸盒对应物品，纸盒的高度对应物品的大小，H对应箱子的容量，于是问题转化为把n个大小为S(i)的物品装到多个容量为H的箱子中，使所使用的箱子的数量最少。


以下摘自《数据结构，算法与应用-C++描述》第10章第5节
--------------------------------------------------
箱子装载问题和机器调度问题（见8.5.2节）一样，也是NP-复杂问题。因此可用近似的算法求解。在箱子装载问题中，该算法可得到一个接近于最少箱子个数的解。对于箱子装载问题，有4种流行的求解算法：
1) 最先匹配法（First Fit, FF）
物品按1，2，?，n的顺序装入箱子。假设箱子从左至右排列。每一物品i放入可盛载它的最左箱子。
2) 最优匹配法（Best Fit, BF）
设cAvail[j]为箱子j的可用容量。初始时，所有箱子的可负载容量为c 。物品i放入具有最小cAvail且容量大于s[i]的的箱子中。
3) 最先匹配递减法（First Fit Decreasing, FFD）
此方法与FF 类似，区别在于各物品首先按容量递减的次序排列，即对于l≤i 4) 最优匹配递减法（ Best Fit Decreasing, BFD）
此法与B F相似，区别在于各物品首先按容量递减的次序排列，即对于l≤i
可以看出，以上4种方法中没有一种能保证获得最优装载。但这4种方法都很直观实用。
--------------------------------------------------

物品数比较少时，可以采用n阶贪婪算法来寻找最优解，当物品比较多时，采用k阶贪婪算法比较好，甚至需要采用一些回溯方法。