278 数字组合（零一背包扩展求方案数目）

偏执的太偏执、 2022-09-10 15:29 98阅读 0赞

**1. 问题描述：**

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

**输入格式**

第一行包含两个整数 N 和 M。  
第二行包含 N 个整数，表示 A1，A2，…，AN。

**输出格式**

包含一个整数，表示可选方案数。

**数据范围**

1 ≤ N ≤ 100，  
1 ≤ M ≤ 10000，  
1 ≤ Ai ≤ 1000，  
答案保证在 int 范围内。

**输入样例：**

4 4  
1 1 2 2

**输出样例：**

3  
来源：[https://www.acwing.com/problem/content/280/][https_www.acwing.com_problem_content_280]

**2. 思路分析：**

由题目的关键字"选"可以知道这道题目属于选择性的问题，对于每一个数字我们可以选择也可以不选择，而且选择的时候是不区分顺序的，由这两个特点可以知道属于经典的**零一背包求解方案数目**的问题（组合类的选择问题）；对于零一背包问题我们可以定义一个一维数组或者列表dp，其中dp\[i\]表示和为i的方案数目，怎么样进行状态的计算呢？状态计算对应集合的划分，对于零一背包问题我们根据选还是不选当前的数字可以划分为两个子集，当我们不择当前数字的时候方案数目为dp\[i\]，当选择当前数字的时候方案数目为dp\[i - v\]，所以和为i的方案数目为dp\[i\] + dp\[i - v\]，因为我们需要使得和恰好为M，所以在初始化的时候dp\[0\] = 1，其余的dp\[i\]都为0表示不合法的状态，这样可以保证最终的dp\[M\]是由一开始的dp\[0\]状态转移得到的。

**3. 代码如下：**

if __name__ == '__main__':
        # n表示n个正整数, m表示数字之和为m
        n, m = map(int, input().split())
        nums = list(map(int, input().split()))
        dp = [0] * (m + 1)
        # 当没有数字的时候也属于合法方案, 为1
        dp[0] = 1
        for i in range(n):
            v = nums[i]
            for j in range(m, v - 1, -1):
                dp[j] += dp[j - v]
        print(dp[m])

[https_www.acwing.com_problem_content_280]: https://www.acwing.com/problem/content/280/