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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
多重集组合数(动态规划(DP))
注:文章内容源自《挑战程序设计竞赛》(第二版) 原题 多重集组合数 有 n 种物品,第 i 种物品有 ai 个。不同种类的物品可以相互区分但是相同的种类无法区分。从这些物品中取出 m 个的话,有多少种取法?求出方案数模M的余数。 1 1 1 2 样例输入 n=3 m=3 a={ 1,2,3 } M=10000 样例输出 6 (0+0+3,0+1+2,0+2+1,1+0+
POJ 3046 Ant Counting(dp—多重集组合数问题)
 Ant Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3753 Accepted: 1475 Description Bessie was poking around the ant h
多重集组合数问题
参考http://blog.csdn.net/viphong/article/details/48110525题目: 有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
动态规划(01背包、完全背包、多重部分和、LCS、LIS、划分数、多重集组合数)
Learn and Review 动态规划入门
多重集组合数-DP
题目: 有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][j]  表示前i种物品,一共拿了j个
(经典)POJ-3046 多重集组合数
题目大意:蚂蚁牙黑,蚂蚁牙红:有A只蚂蚁,来自T个家族,分别记为ant[i]个。同一个家族的蚂蚁长得一样,但是不同家族的蚂蚁牙齿颜色不同。任取n只蚂蚁(S 题目链接:点击打开链接 分析: 多重集组合数也是由多重背包问题拓展出来的一类经典问题。这里仍然给大家讲2种方法: ①朴素方法: 状态:dp[i][j]:前i种中选j个可以组成的种数 决策:第i种选k个,k=0 转
多重集合的排列与组合
《Introductory Combinatorics Fifth Edition》学习笔记: 多重集合的排列: 设S是有k种不同类型对象的多重集合,每个元素都有无限的重复数。那么s的r排列数目是k^r. 例子:最多有4位的3进制数(3元数)的个数是多少? 分析:3^4=81。 设s是多重集合,有k种类型的对象,且每种类型的有限重复数是n1,n2,……,nk。s的大小是n=n
POJ3046 多重集组合数 dp+前缀和优化+滚动数组 (包含类似优化的小总结)
题意 T种数,每种有a[t]个,总共有A个数。问你取其中X个数作为子集,有多少种这样的子集。计算L<=X<=H的子集数之和,结果mod 1000000 1<=T<=1000, 1<=a[t] <= 100,即1 <= A <= 100000, L<=H<=A 思路 基本想法:可以类比为把求max改为求sum的多重背包,所以基本的递推关系很好写,dp(i,j) = sum dp(i-1)(j-k) 其
多重集组合计数
题目n 种物品,第 i 种物品有ai个。不区分同类物品,从中取出 m 个,问有多少种取法。
动态规划实现组合数
#include using namespace std; int a[10001]; void printf(int n,int m){ a[0]=1; for(int i=1;i<=n;i++){ a[i]=1; for(int j=i-1;j>0;j--){ a[j]=a[j]+a[j-1]; } } cout<<a[m]<<endl; } int main(