打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
多重集组合数
 //多重集组合数
        //有n种物品,第i种物品有a[i]个,从这些物品中取出m个,有多少种取法
        //dp[i+1][j]=取法个数,i-1为物品种数,j为取出个数。从第i种取出j个的取法个数
        // 从前i-1种取出j个的取法(不包含第i种物品)和从前i种物品中包含第i种物品的取出j个的取法=dp[i+1][j]
        //包含第i种物品的取出j个的取法,第i种至少一个,至多a[i]个。从i种物品中取出j-1个,第j个视为在第i种物品中
        //这取出j-1个可以有0到a[i]-1个物品在第i种物品中,这样就是包含第i种物品的取出j个的取法个数
        //但是取出j-1个中也可以有a[i]个物品在第i种物品中,这样就与a[i]-1个物品在第i种物品中的情况重复了,前提是a[i]<=j-1
        //所以要减去第i种取a[i]个的取法即dp[i][j-1-a[i]]前i-1种取j-1-a[i]个,若a[i]>j-1,就不存在重复的问题
        //所以递推关系式为dp[i+1][j]= dp[i][j]+dp[i+1][j-1]-dp[i][j-1-a[i]],
        static void Main()
        {
            int m = int.Parse(Console.ReadLine());
            int n = int.Parse(Console.ReadLine());
            int[] a = { 1, 2, 3 };
            int [,]dp = new int[1000, 1000];
            for(int i=0;i<=m;i++)
                for(int j=0;j<=n;j++)
                {
                    dp[i, j] = 0;
                }
            for (int i = 0; i <= m; i++)
                dp[i,0] = 1;
            for (int i=0;i<m;i++)
                for(int j=1;j<=n;j++)
                {
                    if(j-1-a[i]>=0)
                    {
                        dp[i + 1, j] = (dp[i, j] + dp[i + 1, j - 1] - dp[i, j - a[i] - 1]);
                        
                    }
                    else
                    {
                        dp[i + 1, j] = (dp[i, j] + dp[i + 1, j - 1]);
                       
                    }
                }

            
            Console.WriteLine(dp[3, 3]);
            Console.Read();
        }
    }
    //有时候是求余数,在循环里取余,避免溢出,偶尔加上除数避免结果出现负数
}

本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
五大常见算法策略之——动态规划策略(Dynamic Programming)
n个数排序
(六)多重背包-- 二进制位压缩解法--一维数组解析
C# 09.找最大和最小的数字
0-1背包 (20分)
645,动态规划解一和零
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服