2 sinat 29124593 sinat_29124593 于 2016.02.07 10:15 提问

动态规划(多重集组合数)

有n种物品,第i种物品有ai个。不同种类的物品可以互相区分但相同种类的无法区分。从
这些物品中取出m个的话,有多少种取法。
int main()
{
while(cin >> n >> m){
for(int i = 0;i < n;i++){
cin >> a[i];
}
int M;

    cin >> M;
    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; //
                这句话什么意思~~求大神指教(他为什么能到了a[i]+1个,不是就a[i]个吗)
            else{
                dp[i+1][j] = dp[i][j] + dp[i+1][j-1];//还有这句 
            }
        }
    } 
printf("%d\n",dp[n][m]);
}   
return 0;

}

6个回答

caozhy
caozhy   Ds   Rxr 2016.02.08 09:05

简单说下思路,就是从前往后,每一个物品取有0~i个取法,只要没有取够N,就再取下一种物品。
最后把这些可能性叠加下就成了。

caozhy
caozhy   Ds   Rxr 2016.02.08 09:06

调用方式:
foo(N, 1, M)

caozhy
caozhy   Ds   Rxr 2016.02.08 09:04

这个程序因为只要统计个数,不需要那么麻烦,递归下就可以了

 #include <iostream>
using namespace std;

int foo(int n, int idx, int m)
{
    if (m == 0) return 1;
    int sum = 0;
    for (int i = 0; i <= idx && i <= m && idx <= n; i++)
    {
        sum += foo(n, idx + 1, m - i);
    }
    return sum;
}

int main()
{
    cout << foo(4, 1, 2) << endl;
}
qq_33233586
qq_33233586   2016.04.16 10:55

两个都不对,你们安生点吧。

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.02.07 14:43

例如: 有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]

sinat_29124593
sinat_29124593 前i+1种物品取出j个 = 前i+1种物品取出j-1个 + 前i种物品取出j个 - 前i种物品中取出j-1-a个. 因为取出j-1-a个, 最后需要j-1个, 则a需要全部取出, 前两个相重复, 则必然全部取出.这个有点绕,能举个例子吗?
接近 2 年之前 回复
91program
91program   Ds   Rxr 2016.02.07 11:41

下标是否越界的问题,计算一下循环的边界值就可以确定。

91program
91program 回复caozhy: 孙子,你又来找骂!爷爷说过你跟我的回复一下、爷爷就骂一次。这是我对你的“承诺”!无论我的回答正确与否,也无论你的跟的正确与否。骂人,以后升级了:我会骂一片,包括你的家人。Are you ready!天作孽犹可活,自作孽不可活!
接近 2 年之前 回复
91program
91program 回复caozhy: 孙子,大年初一就找骂。你爷爷给出的答案,是一种方法。
接近 2 年之前 回复
caozhy
caozhy 请管理员删除删除这种垃圾回复。
接近 2 年之前 回复
91program
91program 回复91program: 初始化时是小于等于n,后续的循环是小于n,所以可以n+1
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!