多重集组合数 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 有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 <stdio.h>
#include <memory.h>

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<n; ++i) {
			for (int j=1; j<=m; ++j) {
				if (j-1-a[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\n", dp[n][m]);
	}
};

int main(void)
{
	Program iP;
	iP.solve();

	return 0;
}

输出:

result = 6

编程算法 - 多重集组合数 代码(C)