m筐n苹果要几个都可以拿筐数的问题

问题描述, m个筐的(集合表示M),n个苹果,1<=m<=n.
在每个筐中都至少放一个苹果,则筐i中有m(i)个苹果 (1<=i<=m, mi >=1, sum(m(i)) == n).
对于任意给出的k, 1<=k<=n, 都满足能找到一个M的子集, 这些筐中的苹果总数正好是k.
  i' 是 M'中对应M的坐标, M'属于M, 满足sum(m(i')) == k
要求:给出给定(m,n)对应的所有解.

放的结果是一组数字,不用关心顺序,那么对于任意的解,都可以表示成一个[非严格递增序列].
比如5个苹果3个筐,可以的解是[1,2,2],[1,1,3]. 而[3,1,1]和[1,1,3]是等价的.所以解有2个.

从第一个筐开始放,当已经放好了k个筐时,一共放了h个苹果,第k个筐有r个苹果,并且满足子问题(k,h)
那么第k+1个筐中可选的苹果数r'必须满足
 {r' | r <= r' <= h+1, h+r' <= n}     ...................(1)
证明:
 因为前k个筐的h个苹果可以表示[1,h]区间内的数,
 而新加进来的r'和前解做加法,可以表示[1+r',h+r']范围内的数,
 加上r'本身,r'加入后能够表示的区间是([1,h] 并 [r',h+r']). 要保证这一区间连续才能是有效解.
 所以选择r'<=h+1.
 又因为需要是递增序列,所以r'要不小于r, 并且还要有足够的苹果可供使用.
这样递归地求解子问题就可以得出所有的组合了.

启动:为了表示1,第一步可以直接放入一个苹果,或者在第0个筐中放入0个苹果也能满足递归要求,0号筐并不存在.
递归解:如果进行到最后一步,所剩的苹果如果满足(1)的条件,那么返回唯一解,如果不满足,则返回空解.
如果子问题返回空解,则对应的选择无可行解,返回空解.
剪枝:在(1)的情况下,如果还剩x个苹果和y个筐,
 判断: y * r <= x <= (h+1) * (2^y -1), 如果为假,则停止递归,返回空解.
证明:
 按照递增要求,如果k筐有r个苹果,则剩下的每个框都至少有r个苹果
 按照(1)中的区间要求k+1筐中最多有h+1个苹果,k+2中最多有(h+(h+1)) + 1个苹果就是2*(h+1),
   依次每个框中最多的苹果翻倍,求和得到后面可放苹果的上界,也就是判断的右半部分.