经常有点小迷糊
2021-08-28 09:27
采纳率: 92.3%
浏览 36

求和这道题怎么做,给代码(C++)


OICoder的“帅帽”给“师帽”出了一道题,考核师帽上课是否认真听讲。

帅帽给出N个数,要求师帽在这N个数中找出若干个数, 使得它们的和是M。



举个栗子:

若a[i] + a[k] = M,  则说明(a[i], a[k])这个组合符合题意。 

请注意!(a[i], a[k]) 和 (a[k], a[i]) 属于同一种组合方案。



请问一共有多少种数字组合,使得和为M。



输入格式
第一行是两个数字,表示N和M。

第二行起是N个数。(N个数中存在相同的数值,在此题中将他们看作不同的数)



输出格式
一个数字,表示和为M的组合的个数。



输入样例
3 3

2 1 1



输出样例
2

样例解释
第1个数和第2个数和为3,这是第1种组合。

第1个数和第3个数和为3,这是第2种组合



数据范围
1<N<1000

1<M<10000
  • 好问题 提建议
  • 收藏

1条回答 默认 最新

  • 已采纳
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n,m;cin>>n>>m;
        int dp[m+5]={0};
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            int a;cin>>a;
            for(int j=m;j>=a;j--)
            {
                dp[j]+=dp[j-a];
            }
        }
        cout << dp[m] ;
        return 0;
    }
    

    img

    已采纳该答案
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题