摘要
Title: 278. 数字组合
Tag: 01背包
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

278. 数字组合

• 题意

  给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

• 思路

  01背包问题求方案数

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-04-02 16:44:11
  FilePath: \ACM\Acwing\278.py
  LastEditTime: 2022-04-02 16:44:11
  '''
  N = int(1e2 + 10)
  M = int(1e4 + 10)
  f = [0] * M
  
  n, m = map(int, input().split())
  v = list(map(int, input().split()))
  v = [0, *v] #一定要下标从1开始，因为0处是临界条件
  
  f[0] = 1
  for i in range(1, n + 1):
      for j in range(m, v[i] - 1, -1):
          f[j] += f[j - v[i]]
  
  print(f[m])