给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000),sum(1 ≤ sum ≤ 1000)
第二行为n个正整数A[i](32位整数),以空格隔开。
输出所求的方案数
5 15 5 5 10 2 3
4
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])
动态规划算法,有点意思的是每次动态规划保存的是一个字典。
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)
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))
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])
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])
常规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])
# 最优化方案:时间复杂的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])