編程算法 - 多重集組合數 代碼(C)
多重集組合數 代碼(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
