苹果放置 #

1. 苹果放置问题的介绍
2. 苹果放置问题的算法分析
3. 苹果放置问题代码实现

苹果放置问题的介绍 #

将M个苹果放在N个同样的盘子里面，允许有的盘子空着不放，问一共有多少种不同的分法？5，1，1和1，5，1是同一种分法。

苹果放置问题的算法分析 #

该例基本是277课数字拆分问题的延深，又稍有不同。苹果放置时确定每一条路径所需的步骤数就是N，但是允许苹果放置的个数为零，将数字拆分问题稍加改进:
1.第一步:从1~M 的整数中任意选取一个数i，保存这一结果，并使 m=m-i
2.第二步:判断 m 是否为零，如果不为零继续从 1~m 的整数中任意选取一个不小于上一步的数，直到 m 为零
3.如果步数不超过8，输出结果

苹果放置问题的代码实现 #

res=[0]#res[1],保存第一步的解过依次类推
def dfs(m,n,step=1):#定义回溯函数dfm(m,step),m为需要放置的苹果树，n盘子数，step代表每一步，默认值为1
    if m==0: #苹果个数为零
        if(step<=n+1):
            print(res[1:])
        return
    for i in range(1,m+1):
     if(i>=res[step-1]):#当前步骤的选择不小于上一步骤的选择，第一步时大于res[0]
        res.append(i)#保存结果
        m=m-i
        dfs(m,n,step+1)
        res.pop()#取消结果
        m=m+i
dfs(7,3)

事实上上述算法对比数字拆分问题仅仅是对输出的结果进行了筛选，并没有对回溯的过程进行优化。因为我们已经得知了路径的最大深度，基于此我们可以对回溯做出如下改进：
1.第一步:从1~M 的整数中任意选取一个数i，保存这一结果，并使m=m-i
2.第二步:判断 m 是否为零或者 step 是否大于 n，满足任一条件则结束改路径返回，满足题目条件则输出，否则继续选取一个不小于上一步的数

小结 #

• 根据苹果放置问题，理解回溯算法的思想
• 掌握使用已经条件，尽量减小递归深度来对回溯算法进行优化的思路

习题 #

1. 请使用python，将改进的苹果放置问题回溯算法进行实现?
2. 对于上述苹果放置问题，我们可以M个苹果，先放进N-1个盘子里，剩下的放入最后一个盘子，基于此使用python实现算法?