我要招人

去企业版

首页 > 试题广场 >

数字和为sum的方法数

[编程题]数字和为sum的方法数

热度指数：23886 时间限制：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

输出

算法知识视频讲解

Python

软皮鞋跟

这道题我的矩阵维数是5*16维. 而不是高赞回答里的6*16, 他的方法里矩阵的第一行可以省略, 方法借鉴https://www.bilibili.com/video/av18512769?t=219 里的第二题(15分52秒开始).

n, sums = map(int, input().split())
arr =  list(map(int, input().split()))
res = [[1 if i == 0 else 0 for i in range(sums + 1)] for j in range(n)]
res[0][arr[0]] = 1
for i in range(1, n):
    for j in range(1, sums + 1):
        if arr[i] <= j:
            res[i][j] = res[i-1][j] + res[i-1][j-arr[i]]
        else:
            res[i][j] = res[i-1][j]
print(res[-1][-1])

发表于 2019-09-07 19:24:34 回复(0)

Python

冉龙宇

动态规划算法，有点意思的是每次动态规划保存的是一个字典。

nsum = list(map(int, input().strip().split()))
sum = nsum[1]
nli = list(map(int, input().strip().split()))

def find(nli, sum):
    lastdi = {}  # 上一次的方案数
    for num in nli:
        thisdi = {}
        if not lastdi.get(num):  # 先考虑num的情况
            if num<=sum:
                thisdi[num] = 1
        else:
            if num+num<=sum:
                thisdi[num + num] = lastdi[num]
            thisdi[num] = lastdi[num] + 1
        for k,v in lastdi.items():
            if k!=num:
                if not thisdi.get(k):
                    thisdi[k] = v
                else:
                    thisdi[k] += v
                if k + num <= sum:
                    if not thisdi.get(k+num):
                        thisdi[k + num] = v
                    else:
                        thisdi[k+num] += v
        lastdi = thisdi
    return lastdi.get(sum)

result = find(nli, sum)
if result:
    print(result)
else:
    print(0)

发表于 2019-08-27 11:24:31 回复(0)

Python

白色纯度

python3 动态规划的解法：

dp矩阵优化为二维矩阵

def solve(num,m):
    dp = [[0 for _ in range(m+1)] for _ in range(2)]
    dp[0][0],dp[1][0] = 1,1
    i = 0
    while i < len(num):
        for j in range(1,m+1):
            dp[1][j] = dp[0][j]
            if num[i]<=j:
                dp[1][j] += dp[0][j-num[i]]
        i += 1
        dp[0] = [k for k in dp[1]]
    return dp[-1][-1]
if __name__=='__main__':
    n, m = list(map(int,input().split()))
    num = list(map(int,input().split()))
    print(solve(num,m))

超时的递归解法：（50%通过率）

def solve(num,m,res):
    tmp = [i for i in res]
    if m==0:
        ans.append(tmp)
    elif m<0:
        return
    if not num:
        return
    for i in range(len(num)):
        if num[i]<=m:
            res.append(num[i])
            new = num[i+1:]
            solve(new,m-num[i],res)
            res.pop()
if __name__=='__main__':
    n, m = list(map(int,input().split()))
    num = list(map(int,input().split()))
    ans = []
    solve(num,m,[])
    print(len(ans))

发表于 2019-08-24 23:26:17 回复(0)

Python

lx的流星

运用动态规划可以求出来，结合多位大神的思想写的Python代码

while True:

try:
list1=input().split(' ')

n=int(list1[0])
m=int(list1[1])
A=list(map(int,input().split(' ')))
list1=[]
for i in range(m+1):
list1.append(i)
dp=[]
for i in range(n+1):
dp.append([0]*(m+1))
#创建dp矩阵
for i in range(m+1):
dp[0][i]=0
for i in range(n+1):
dp[i][0]=1
#初始化dp矩阵
for i in range(1,n+1):
for j in range(1,m+1):
if A[i-1]>j:
dp[i][j]=dp[i-1][j]

else:
dp[i][j]=dp[i-1][j]+dp[i-1][j-A[i-1]]
#print(dp)

result=dp[-1][-1]
print(result)
except:
break

编辑于 2019-05-21 09:45:15 回复(0)

Python

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

离疏

n,sums=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[0 for i in range(sums+1)]#假设dp[sum]表示部分数组和恰好为sum的方案数
for i in range(n):
    if a[i]>sums:
        continue
    for j in range(sums-a[i],0,-1):#对于每一个a[i],我们更新所有的dp[1...sum],即，dp[j+num[i]] += dp[j]
        if dp[j]>0:
            dp[j+a[i]]+=dp[j]
    dp[a[i]]+=1
print(dp[sums])

发表于 2018-06-25 14:31:38 回复(0)

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)

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)

Python

李帆

#Pass rate 20%, timeout

import sys
data=[]
for line in sys.stdin:
data.append([int(i) for i in line.strip('\n').split()])
num=data[0][0]
summ=data[0][1]
data=data[1]

def find(data,summ):
    count=0
    if summ==0:
        return 1

    if summ<0 or len(data)==0:
        return 0
    for i in range(len(data)):
        count+=find(data[i+1:],summ-data[i])
    return count
print(find(data,summ))

编辑于 2017-09-01 19:24:26 回复(0)