多重集组合数 代码(C)

?

?

题目: 有n种物品, 第i种物品有a个. 不同种类的物品可以互相区分, 但相同种类的无法区分.

从这些物品中取出m个, 有多少种取法? 求出数模M的余数.

例如: 有n=3种物品, 每种a={1,2,3}个, 取出m=3个, 取法result=6(0+0+3, 0+1+2, 0+2+1, 1+0+2, 1+1+1, 1+2+0).

?

使用动态规划(DP).

前i+1种物品取出j个 = 前i+1种物品取出j-1个 + 前i种物品取出j个 - 前i种物品中取出j-1-a个.

因为取出j-1-a个, 最后需要j-1个, 则a需要全部取出, 前两个相重复, 则必然全部取出.

递推公式: dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a]

时间复杂度O(nm).

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     class Program { static const int MAX_N = 100; int M=10000; int n=3, m=3; int a[MAX_N] = {1,2,3}; int dp[MAX_N+1][MAX_N+1]; public: void solve() { for (int i=0; i<=n; ++i) { dp[i][0] = 1; } for (int i=0; i
    
     = 0) { dp[i+1][j] = (dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]+M)%M; } else { dp[i+1][j] = (dp[i+1][j-1]+dp[i][j])%M; } } } printf(result = %d , dp[n][m]); } }; int main(void) { Program iP; iP.solve(); return 0; } 
    
   
  

?

输出:

?

result = 6

?

?

?