首页 > 试题广场 >

数字和为sum的方法数

[编程题]数字和为sum的方法数
  • 热度指数：23872 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

输入描述:
输入为两行:
 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
 第二行为n个正整数A[i](32位整数)，以空格隔开。


输出描述:
输出所求的方案数
示例1

输入

5 15 5 5 10 2 3

输出

4
算法知识视频讲解
添加回答
初日晨曦头像 初日晨曦 
//递归会超时，只能过40%，用dp. dp[i][j]表示用前i个值组成和为j的方案个数（相比一维的，更容易理解一些）
#include <iostream>
#include <algorithm>
using namespace std;
//注意：最终结果int类型存不下，需要64位数据
//注意：dp不能放在main里，栈存不下。需要存在全局数据区
long long dp[1001][1001];
int main()
{
	int n,sum;
	cin>>n>>sum;

	int p[1000];
	for(int i = 1 ; i <= n ; i++)
		cin>>p[i];
//初始化dp,用前i个组成和为0的方案，只有1种，就是什么都不取，和为0；
	for (int i = 0 ; i < n ;i++)
	{
		dp[i][0] = 1;
	}
//用0个元素不能组成1~sum
	for (int j = 1 ; j < sum ;j++)
	{
		dp[0][j] = 0;
	}

	for (int i = 1 ; i <= n ;i++)
	{
		for (int j = 0 ; j<=sum ;j++)
		{
			if(p[i]<=j) dp[i][j] = dp[i-1][j]+dp[i-1][j-p[i]];
			else dp[i][j] = dp[i-1][j];
		}
	}
	cout<<dp[n][sum]<<endl;
	return 0;
}

编辑于 2018-09-17 09:26:34 回复(15)
C/C++
骏博日博的迷弟头像 骏博日博的迷弟
这题没得说，看到sum的范围为1000就该dp了。。 
#include <cstdio>
#include <algorithm>
#include <cstring>
long long dp[1002][1002];
int main()
{
	int n;
	int A[1002];
	int sum;
	while (scanf("%d %d", &n, &sum) != EOF)
	{
		for (int i = 0; i<n; i++)
			scanf("%d", A + i);
		for (int i = 0; i <= sum; i++)
			dp[0][i] = 0;
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j <= sum; j++)
			{
				dp[i][j] = dp[i - 1][j];
				if (j >= A[i-1])
					dp[i][j] += dp[i - 1][j - A[i-1]];
			}
		}
		printf("%lld\n", dp[n][sum]);
	}
	return 0;
}

发表于 2017-08-08 20:58:02 回复(4)
张瑞泽头像 张瑞泽
动态规划算法。dp[i][j]代表用前i个数字凑到j最多有多少种方案。
dp[i][j]=dp[i-1][j];   //不用第i个数字能凑到j的最多情况
dp[j][j]+=dp[i-1][j-value[i]];  //用了i时，只需要看原来凑到j-value[i]的最多情况即可。并累加
dp[0]=1;  //初始化，表示凑到0永远有1种方案。
按01背包的思路写循环即可。 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int sum = in.nextInt();
        int[] value = new int[n];
        long[] dp = new long[sum + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            value[i] = in.nextInt();
            for (int j = sum; j >= 0; j--) {
                if (j >= value[i]) {
                    dp[j] += dp[j - value[i]];
                }
            }
        }
        System.out.println(dp[sum]);
    }
}

发表于 2017-04-04 09:19:38 回复(3)
月缘天星头像 月缘天星 
 
/*
 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 
   解：此题使用递归的遍历方法也可以解决，但是会超时
   dp解决：
   以每个物品作为横轴，以背包容量作为纵轴
       0 1 2 3 4 5 6..........
     0 1 0 0 0 0 0 0..........
     5 1 0 0 0 0 1 0
     
      其中1表示前n件物品放入容量为M的背包有1种方法，（5，0）表示重量为5的物品放入容量为0的背包的背包有1中方法，即不放入。0表示恰好放满背包的方法为0
      当M>weight[i]时，dp[M]=dp[M]+dp[M-weight[i]];意义是：放入物品i和不放入物品i的方法总和
 */
import java.util.*;
public class Main{
    public static long bag(int []weight,int n,int sum){
        long dp[]=new long[sum+1];
        dp[0]=1;
        int i,j;
        for(i=0;i<n;i++){
            for(j=sum;j>=weight[i];j--){
               dp[j]=dp[j-weight[i]]+dp[j];
            }
        }
        return dp[sum];
    }
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int sum=s.nextInt();
        int i,j;
        int arr[]=new int[n];
        for(i=0;i<n;i++){
            arr[i]=s.nextInt();
        }
        System.out.println(bag(arr,n,sum));
    }
}

发表于 2017-01-26 11:29:55 回复(6)
C/C++
卷积神经网络哦头像 卷积神经网络哦

最简单的是一维动态规划  0-1背包问题变种 求方法数 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//常量区
const int maxn = 1e3 + 5;
int A[maxn], n, sum;
long long dp[maxn];
//main函数
int main(){
    scanf("%d%d", &n, &sum);
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = sum; j >= A[i]; j--)
            dp[j] = dp[j] + dp[j - A[i]];         
    printf("%lld\n", dp[sum]);
    return 0;
}
/*
5 15
5 5 3 2 10
ans : 4
*/
编辑于 2018-09-17 21:31:01 回复(0)
袁博文202头像 袁博文202
python3代码， 动态规划
递推关系为
dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]]
其中i表示数组下标，j表示和为j，dp[i][j]表示前i个元素和为j的方案数
由于递推关系dp[i][j]只与i-1有关，因此空间复杂度可以优化为O(n)
每次的递推数组dp可以由自身得到，循环下标j从m往小循环 
n, m = [int(i) for i in input().split()]
a = list(map(int,input().split()))
dp = [0 for i in range(m+1)]
dp[0] = 1
for i in range(n):
    j = m
    while j>=a[i]:
        dp[j] += dp[j-a[i]]
        j -= 1
print(dp[m])

发表于 2017-10-28 15:47:38 回复(0)
Python
吉事有祥头像 吉事有祥 
# 最优化方案：时间复杂的O(n*sum), 空间复杂度(sum)
n, sum = list(map(int,input().split()))
A = list(map(int,input().split()))

if sum == 0:
    print(1)
else:
    s = [0 for _ in range(sum)]
    for i in range(n):
        if A[i] > sum:
            continue
        for j in range(sum-1-A[i], -1, -1):
            if s[j] > 0:
                s[j + A[i]] += s[j]
        s[A[i]-1] += 1
    print(s[-1])

发表于 2017-09-28 11:36:39 回复(0)
Java
hello古斯卡头像 hello古斯卡 
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner cin = new Scanner(System.in);

		int n = cin.nextInt();
		int m = cin.nextInt();

		int arr[] = new int[n+1];
                //代表你使用前i个数组组成j的最大组合数
		long dp[][] = new long[n + 1][m + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = cin.nextInt();
		}

		
		for (int i = 0; i < m; i++) {
			dp[0][i] = 0;
		}
		//注意，你的dp[0][0]一定要是1，否则会出错
		for (int i = 0; i < n; i++) {
			dp[i][0] = 1;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (arr[i] <= j) {
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]];
				} else {
					dp[i][j] = dp[i - 1][j];
				}
				
			}
			
		}

		System.out.println(dp[n][m]);
	}

}

发表于 2017-09-06 02:34:18 回复(0)
wangwenbin头像 wangwenbin 
// 这应该也算是一个动态规划的问题
// 假设dp[sum]表示部分数组和恰好为sum的方案数
// 因此 dp[sum] = dp[sum-num[1]] + ... dp[sum-num[n]]
// 所以要求dp[sum], 需要求所有的dp[0...sum-1]的方案数
// 实际编程的时候我们不这么计算
// 对于每一个num[i],我们更新所有的dp[0...sum],即，dp[k+num[i]] += dp[k]
// 表达的意思就是假设已经知道dp[k]的方案数，那么num[i]使dp[k+num[i]]增加的方案数肯定是再加上dp[k]的方案数。
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int sum = sc.nextInt();
            int[] num = new int[n];
            for(int i=0;i<n;i++){
                num[i] = sc.nextInt();
            }
            long[] count = new long[sum+1];
            count[0] = 1;
            for(int i=0;i<n;i++){
                if(num[i]<=sum){
                    for(int j=sum;j>=0;j--){
                        if(count[j]>0 && j+num[i]<=sum){
                            count[j+num[i]] += count[j];
                        }
                    }
                }
            }
            System.out.println(count[sum]);
        }
    }
}






编辑于 2017-09-05 10:59:04 回复(1)
古典文化头像 古典文化 
import java.util.*;
public class sumA {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
        	int n = input.nextInt();
        	int m = input.nextInt();
        	int[] arr = new int[n];
        	for(int i = 0; i < n; i++) {
        		arr[i] = input.nextInt();
        	}
        	long[][] dp = new long[n][m + 1];
        	dp[0][0] = 1;
        	if(arr[0] <= m) {
        		dp[0][arr[0]] = 1;
        	}
        	for(int i = 1; i < n; i++) {
        		for(int j = 0; j <= m; j++) {
        			if(j - arr[i] < 0) {
        				dp[i][j] += dp[i - 1][j];
        			}
        			else {
        				dp[i][j] += dp[i - 1][j - arr[i]] + dp[i - 1][j];
        			}
        		}
        	}
        	System.out.println(dp[n - 1][m]);
        }
        input.close();
	}
}


发表于 2017-08-17 22:12:01 回复(2)
Jimmy_gg头像 Jimmy_gg 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

long long dp[1005][1005];
int main()
{
    using namespace std;
    int n, sum;
    while (cin >> n >> sum) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        for (int i = 0; i < sum; i++) {
            dp[0][i] = 0;
        }
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (nums[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        cout << dp[n][sum] << endl;
    }
    return 0;
}
参考优秀回答的二维dp解法
发表于 2017-06-22 11:05:27 回复(1)
YoHoooo头像 YoHoooo

#include <iostream>

using namespace std ;

long long dp[ 1001 ];

int w[ 1001 ];

bool islegal( int j)

{

    if (j>= 0 ) return true ;

    return false ;

}

int main()

{

    int n,sum;

    while ( cin >>n>>sum){

        for ( int i= 1 ;i<=n;++i)

            cin >> w [i];

        

        //dp(j)=dp(j)+dp(j-w[i])    dp(0)=1

        for ( int j= 0 ;j<=sum;++j)

            if (j== 0 )

                dp [j]= 1 ;

            else dp [j]= 0 ;

        for ( int i= 1 ;i<=n;++i)

        {

            for ( int j=sum;j>= 0 ;--j)

            {

                if ( islegal (j- w [i]))

                    dp [j] = dp [j]+ dp [j- w [i]];

            }

            

        }

        cout << dp [sum]<< endl ;

    }

    return 0 ;

}

发表于 2017-01-28 19:00:41 回复(0)
Tianxn头像 Tianxn 
// 数字和为sum的方法数
/*
知识普及：
    最值型0-1背包：dp[j] = max/min(dp[j], dp[j-w[i]] + v[i])
    布尔型0-1背包：dp[j] |= dp[j-w[i]];
    计数型0-1背包：dp[j] += dp[j-w[i]]; 注意：一般需要开long long
本题对应：
    物品：n个正整数
    体积：每一个数字的大小
    价值：无
    背包容量：数字和sum
状态表示：
    dp[i][j]表示前i个数字能凑成和为j的方案数
状态转移：
                dp[i-1][j]             不选择第i个数字
    dp[i][j] =
                dp[i-1][j-w[i]]        选择第i个数字
    降维合并：
    dp[j] += dp[j-w[i]];
初始状态：
    dp[0] = 1;
最终结果：
    dp[sum]
*/
#include 
using namespace std;
int n, x, sum;
long long dp[1005];
int main()
{
    cin >> n >> sum;
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x;
        for (int j = sum; j >= x; --j)
            dp[j] += dp[j-x];
    }
    cout << dp[sum] << endl;
    return 0;
}
发表于 2021-08-10 10:12:00 回复(0)
Debug丶头像 Debug丶 
要用long long才不溢出。。。。
#include <iostream>
using namespace std;

int main()
{
    int nCount, nSum;
    while (cin >> nCount >> nSum)
    {
        if (nCount < 1 || nCount > 1000 || nSum < 1 || nSum > 1000)
        {
            cout << 0 << endl;
            continue;
        }
        int* pNums = new int[nCount];
        long long** pDP = new long long*[nCount];
        for (int i = 0; i < nCount; ++i)
            pDP[i] = new long long[nSum + 1]();
        for (int i = 0; i < nCount; ++i)
            cin >> pNums[i];
        if (nSum >= pNums[0])
            ++pDP[0][pNums[0]];
        for (int i = 1; i < nCount; ++i)
        {
            for (int j = 1; j <= nSum; ++j)
            {
                if (j >= pNums[i])
                    pDP[i][j] = pDP[i - 1][j - pNums[i]] + pDP[i - 1][j];
                else
                    pDP[i][j] = pDP[i - 1][j];
            }
            if (nSum >= pNums[i])
                pDP[i][pNums[i]] = pDP[i - 1][pNums[i]] + 1;
        }
        cout << pDP[nCount - 1][nSum] << endl;
        for (int i = 0; i < nCount; ++i)
            delete[] pDP[i];
        delete[] pNums;
    }
}

发表于 2019-08-26 15:40:56 回复(0)
胖十斤换网名的阿琛头像 胖十斤换网名的阿琛 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
int A[1024] = {0};
ll dp[1024] = {1};
int main()
{    int n, m;    while (cin >> n >> m)
      {
        for(int i = 1;i <= n;i++)scanf("%d",&A[i]);
       for(int i = 1;i <= n;i++)for(int j = m;j >= A[i];j--)
        dp[j] += dp[j - A[i]];
      cout << dp[m] << endl;    }  return 0;
}

编辑于 2019-07-07 21:57:36 回复(0)
Java
handsome_an头像 handsome_an

动态规划
设m[i][j]是前i个数 和为j的的最大组合方案数
递归公式
1 j=0 //j-a[i]为0时,表示a[i]=j,组合数为1
0 j<0
0 i<1且j!=0
M[i][j]=M[i-1][j]+M[i-1][j-a[i]] //前i-1个 和为j的最大组合数 + 前i-1个 和为 j-a[i]的最大组合数
例如 n=7 sum=8
数据为:5 1 2 4 3 2 3
得到如下矩阵
(i\j) 0 1 2 3 4 5 6 7 8
0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0
2 1 1 0 0 0 1 1 0 0
3 1 1 1 1 0 1 1 1 1
4 1 1 1 1 1 2 2 2 1
5 1 1 1 2 2 3 3 3 3
6 1 1 2 3 3 5 5 6 6
7 1 1 2 4 4 7 8 9 11
例如:m[7][9]=m[6][8]+m[6][8-3]=11
由于当前行只用到了上一行的数值,固可用二维数组存储

    public static void main(String[] args)throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String[] strings=br.readLine().split("\\s");
        int n=Integer.parseInt(strings[0]);
        int sum=Integer.parseInt(strings[1]);
        strings=br.readLine().split("\\s");
        int[]data=new int[n];
        for(int i=0;i<n;i++){
            data[i]=Integer.valueOf(strings[i]);
        }
        dp(n,sum,data);
    }
    private static void dp(int n,int sum,int [] data){
        long[][] m=new long[2][sum+1];
        m[0][0]=1;//j=0
        m[1][0]=1;//j=0
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum;j++){
                if(j>=data[i-1]){
                    m[1][j]=m[0][j]+m[0][j-data[i-1]];
                }else {
                    m[1][j]=m[0][j];
                }
            }
//            System.out.println(Arrays.toString(m[0]));

            for(int k=0;k<=sum;k++){
                m[0][k]=m[1][k];
            }
        }
//        System.out.println(Arrays.toString(m[0]));
        System.out.println(m[0][sum]);
    }
发表于 2018-12-08 18:46:44 回复(0)
Python
Zoom内推助手头像 Zoom内推助手
Python3 solution 
n, sum_wanted = map(int, input().split())
l = [0] + list(map(int, input().split()))
res = [[1 if i == 0 else 0 for i in range(sum_wanted + 1)] for  j in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, sum_wanted + 1):
        if l[i] <= j:
            res[i][j] = res[i-1][j]+res[i-1][j-l[i]]
        else:
            res[i][j] = res[i-1][j]

print(res[n][sum_wanted])

发表于 2018-08-01 12:55:40 回复(1)
Python
新鲜菜鸡🐔头像 新鲜菜鸡🐔

常规DP，dp[sum][i] = dp[sum-num[i]][i-1]+dp[sum][i-1] i表示只考虑前i个数。

N,sum_x= map(int,input().split())
list_x = [int(x) for x in input().split()]
len_x = len(list_x)
ans = [[0 for i in range(N+1)] for j in range(sum_x+1)]

for i in range(N+1):
    ans[0][i] = 1
for i in range(1,sum_x+1):
    for j in range(1,N+1):
        if i-list_x[j-1]<0:
            ans[i][j] = ans[i][j-1]
        else:
            ans[i][j] = ans[i][j-1]+ans[i-list_x[j-1]][j-1]
print(ans[-1][-1])
发表于 2018-05-23 23:50:28 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream> 

using namespace std;

int main()
{     long long dp[1003][1003];     int a[1003],n,sum;     while(cin>>n>>sum)     {         for(int i=0;i<n;i++)             cin>>a[i];         for(int i=0;i<=sum;i++)             dp[i][0] = 0;         dp[0][0] = 1;         for(int i=1;i<=n;i++)         {             for(int j=0;j<=sum;j++)             {                 dp[i][j] = dp[i-1][j];                 if(j >= a[i-1])                     dp[i][j] += dp[i-1][j-a[i-1]];             }         }         cout<<dp[n][sum]<<endl;     }     return 0;
}

发表于 2018-01-15 00:19:28 回复(0)
松弦止风头像 松弦止风 
import java.util.*;
class Main{
    private static int[] twoSum(int n, int[] A，int sum){
        Map(Integer, Integer) map = new HashMap<>();
        for(int i =0; i<n; i++) {
            map.put(A[i],i);
        }
        for(int i=0;i<n;i++) {
            int result = sum - A[i];
            if(map.containsKey(result) && map.get(result) !=i) {
                return new int[]{A[i],i};
            }
        }
        throw new IllegalArgumentException("不存在这样的方案");
}
}

发表于 2017-10-01 23:12:02 回复(3)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 滴滴 动态规划 Java工程师
上传者：小小
难度：
88条回答 31488浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号