多重集组合数问题（动态规划）——炎泽汐 の Blog

题目描述

有 n 种物品，第 i 种物品有 a_i 个，不同种类的物品可以互相区分, 但相同种类的无法区分。从这些物品中取出 m 个, 有多少种取法? 求出数模 M 的余数.：

解析

考虑使用动态规划方法进行实现，定义状态方程为：dp[i][j]=前 i 类物品中取出 j 个的组合总数。可以得到以下状态转移方程：

以上递推公式包含三层循环，时间复杂度为 O(n*m^2)，显然是过高了，于是我们考虑进行优化：

首先分为两种情况进行讨论：

       1）j<=a[i]，即(j-1<a[i])时：原式可以展开为 dp[i+1][j]=dp[i][j]+dp[i][j-1]+···+dp[i][0]，可以注意到 dp[i+1][j-1]=dp[i][j-1]+···+dp[i][0]，因此有 dp[i+1][j]=dp[i][j]+dp[i+1][j-1]。

       2）j>a[i]时：原式可以展开为 dp[i+1][j]=dp[i][j]+dp[i][j-1]+···+dp[i][j-a[i]]，注意到 dp[i+1][j-1]=dp[i][j-1]+···+dp[i][j-a[i]-1]，因此 dp[i+1][j]=dp[i][j]+dp[i+1][j-1]-dp[i][j-a[i]-1]。

综上，我们可以得到以下状态转移方程：

代码实现（C++）

#include<bits/stdc++.h>
using namespace std;
 
int n,m,M;
int a[1001];
int dp[1001][1001];
 
int main(){
    cin>>n>>m>>M;
    for(int i = 0;i < n;i++){
        cin>>a[i];
    }
	
    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][j] + dp[i + 1][j - 1] - dp[i][j - 1 - a[i]] + M) % M;
            }else{
                dp[i + 1][j] = (dp[i][j] + dp[i + 1][j - 1]) % M;
            }
        }
    }
	
    cout<<"解为："<<dp[n][m]<<endl;
    return 0; 
}

喜欢 (10)赏

[炎泽汐de收款码]

分享 (0)