什么叫隔板法?-什么叫做隔板法

隔板法是一种优化技术，用于解决背包问题和分治算法中的其他类似问题。它的基本思想是将一个大问题分解成若干个小问题，然后对每一个小问题进行求解，并将这些解组合起来得到原问题的解。

在隔板法中，通常使用二分搜索法来找到最优解。

1.我们将所有物品依照大小排序，然后初始化一个数组来存储每种物品的最大数量。接下来，我们遍历所有物品，并尝试插入它们到现有的隔板之间，以使得当前物品的数量不超过其最大数量。如果可以这样做，我们就增加一个隔板；否则，我们就减少一个隔板。我们返回最后一个隔板的位置，这就是原问题的解。

例如，假定我们有一个背包，其中可以装下20单位的物品。现在有5个物品，它们的重量分别是3、5、7、8和12单位。我们可以先将这5个物品依照重量从小到大排序，然后初始化一个数组来存储每种物品的最大数量。然后，我们从第1个物品开始，尝试将它插入到现有隔板之间，以使得当前物品的数量不超过其最大数量。如果可以这样做，我们就增加一个隔板；否则，我们就减少一个隔板。经过一系列的操作，我们可以得到最优解，即第二个物品应当放在第三个物品之前。这样，我们就得到了一个可以装下19单位物品的背包，剩余的1单位物品不能装进去。

将8个完全相同的球放到3个不同的的盒子中，要求每个盒子至少放一个球，一共有多少种方法？

答案28种。

解析解决这道问题只需要将8个球分成三组，然后依次将每一组分别放到一个盒子中即可。因此问题只需要把8个球分成三组即可，于是可以将8个球排成一排，然后用两个板插到8个球所形成的空里，即可顺利的把8个球分成三组。其中第一个板前面的球放到第一个盒子中，第一个板和第二个板之间的球放到第二个盒子中，第二个板后面的球放到第三个盒子中去。因为每个盒子至少放一个球，因此两个板不能放在同一个空里且板不能放在两端，于是其放板的方法数是

C（8，2）=28种。（注：板也是无区别的）

这个方法在排列组合中叫做“隔板法”。

有问题请追问~~~满意请采纳~~~