• Tag:递归 搜索

    description

    把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

    首先是递归解法(from:http://blog.csdn.net/waterbuffalo/article/details/5972648

    最典型的整数分解,例如给定n个苹果,把苹果放到k个盘子里,允许有的盘子为空(poj1664),不妨设 f(n , k ) (边缘条件为当 n = 0 时,返回1,当 k = 1 时,返回1)表示结果,分析一下可以知道有两中放的方法,一种是有空盘,一种是没空盘,没空盘的情况可以知道每个盘子里至少有一个苹果,也就是说这种情况的总数为 f ( n-k , k ) 。而有空盘的情况,我们可以假设最后一个盘子为空,则这种情况的总数为

    f ( n , k-1 ) (无需考虑多个盘子为空的情况,递归时必然会出现)所以状态转移方程为 f ( n , k ) = f  ( n-k , k ) +  f ( n , k-1 )。

    而如果是不允许有空盘子的情况,则可以由上面的情况推出,设 d ( n , k ) 表示把n个苹果放到k个盘子里,不允许有空盘子的方法总数,则有

    f ( n , k ) =  Σ (  1 <= i <= k ) d ( n , i ) 所以 d ( n , k ) = f ( n , k ) - f ( n , k-1 )

    ==================================================================

    比较难理解的是深搜解法:

    我们定义一个过程,使其反复递归穷举第1份、第2份……第k份,然后寻找出可行的路径,时间复杂度O(nk)。这种方法思路十分便捷,但也许会超时。
    我们有两个很好的剪枝:
    剪枝1如果剩余的够不上最小的则剪去。这是显而易见的常理,但是可以加快速度。剪枝2枚举到剩余1个盘子时判断是否可行。也是加快速度的方法,使在题目所描述的n和k的范围之中完全可行。
    重复的只算一种,我们怎么样处理有关重复的呢?我们可以引入一个参数min,作为至少每一个要达到min,顺序由小而大,逐层递归。
    综上所述,我们可以轻易写出一个优化过的递归搜索程序。

    #include<stdio.h> 
    int sum, n, k, count; 
    void dfs(int step, int min) 

     
        if(step == k + 1
        { 
            if(sum == n)count++; 
            return
        } 
        for(int i = min; i <= n; i++) 
        { 
            sum += i; 
            dfs(step + 1, i); 
            sum -= i; 
        } 
        return

    int main() 

        int t; 
        scanf("%d", &t); 
        count = 0
        while(t--) 
        { 
            scanf("%d%d", &n, &k); 
            sum = 0
            count = 0
            dfs(10); 
            printf("%d\n", count); 
        } 
        return 0