数组中任取几个数字和为sum的方法数

98 阅读 0 评论 65 点赞

我是靠谱客的博主可爱自行车，这篇文章主要介绍数组中任取几个数字和为sum的方法数，现在分享给大家，希望可以做个参考。

题目描述:
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
输入描述:
输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
第二行为n个正整数Ai，以空格隔开。
输出描述:
输出所求的方案数
输入:
5 15 5 5 10 2 3
输出:
4

手撕dfs失败:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void helpf(vector<int>&vr,int pos,int sum,int m,int& res){
    if(sum==m){
        res++;
        return;
    }
    else if(sum>m){
        return;
    }else{
        if(pos<vr.size()){
            sum+=vr[pos];
            helpf(vr,pos+1,sum,m,res);
            sum-=vr[pos];
            helpf(vr,pos+1,sum,m,res);
        }
    }
}

改进为DP:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int main(){
    int n=0;
    int m=0;
    while(cin>>n>>m){
        vector<int> vr(n);
        for(int i=0;i<n;++i){
            cin>>vr[i];
        }
        sort(vr.begin(),vr.end(),greater<int>());
        //      int res=0;
        //      helpf(vr,0,0,m,res);//递归超时,通过率50%
        //      cout<<res<<endl;
        vector<vector<long long int>>dp(n,vector<long long int>(m+1,0));
        for(int i=0;i<n;++i){
            dp[i][0]=1;
        }
        for(int i=1;i<=m;i++){
            if(vr[0]>m)//过滤
                break;
            if(vr[0]==i)
                dp[0][i]=1;
            else
                dp[0][i]=0;
        }
        for(int i=1;i<n;++i){
            if(vr[i]>m)  //过滤
                continue;
            for(int j=1;j<=m;++j){
                if(j-vr[i]>=0)
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-vr[i]];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n-1][m]<<endl;
    }
    return 0;
}