数字和Sum的方案数

比眉伴天荒 2022-05-18 02:19 111阅读 0赞

> ### 题目描述 ###
> 
> 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
> 
> ##### 输入描述: #####
> 
> 输入为两行：  
> 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数Ai，以空格隔开。
> 
> ##### 输出描述: #####
> 
> 输出所求的方案数
> 
> ##### 示例1 #####
> 
> 输入  
> 5 15 5 5 10 2 3  
> 输出  
> 4

#### 方法一：递归+回溯 ####

若子集和为Sum，则方案数加一。

#include<iostream>
    #include<vector>
    using namespace std;
    void help(vector<int>& a, int index, int part, int n, int sum, int &count)
    {
        if (part == sum)
            count++;
        if (part > sum)
            return;
        for (int i = index; i<n; i++) 
        {
            part += a[i];
            help(a, i + 1, part, n, sum, count);
            part -= a[i];
        }
    }
    int main()
    {
        int n, sum;
        int count = 0;
        cin >> n >> sum;
        vector<int> a(n);
        for (int i = 0; i<n; i++)
            cin >> a[i];
        help(a, 0, 0, n, sum, count);
        cout << count << endl;
        return 0;
    }

时间复杂度太高，递归调用次数过多，不适合使用。

#### 方法二：动态规划 ####

类似于[01背包问题][01]  
要么取这个数，要么不取这个数，将两种方案加起来就是总的方案数。公式如下：

j<arr[i]时，dp[i][j] = dp[i-1][j]
    j>=arr[i]时，dp[i-1][j]+dp[i-1][j-arr[i]]

>  *  dp\[i\]\[j\]表示前i个数中和为j的方案数，例如dp\[3\]\[115\]表示前3个数字中和为15的方案数。
>  *  初始条件：dp\[i\]\[0\] = 1，i=0,1,…,n，表示如果和为0，那么一个数字也不用选，这也是一种方案，所以是1。
>  *  上面的公式意思是：如果和`j`小于第i个数字，那么如果选上第i个数字和就大于j了，所以不选第i个数字，方案数等于前i-1个数的方案数：dp\[i\]\[j\] = dp\[i-1\]\[j\]
>  *  如果和`j`大于等于第i个数字，就像我们前面说的，要么选这个数字，要么不选这个数字。如果不选这个数字，方案数和上面一样仍为dp\[i-1\]\[j\]，如果选这个数字，方案数为dp\[i-1\]\[j-arr\[i\]\]，所以方案数为二者之和dp\[i-1\]\[j\]+dp\[i-1\]\[j-arr\[i\]\]

以此题为例，输入`5 15 5 5 10 2 3`，最终的方案数的矩阵如下：

<table> 
 <thead> 
  <tr> 
   <th>index</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
   <th>10</th> 
   <th>11</th> 
   <th>12</th> 
   <th>13</th> 
   <th>14</th> 
   <th>15</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>1[5]</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>2[5]</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>3[10]</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>4[2]</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>5[3]</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
   <td>3</td> 
   <td>0</td> 
   <td>2</td> 
   <td>2</td> 
   <td>0</td> 
   <td>4</td> 
   <td>0</td> 
   <td>2</td> 
   <td>2</td> 
   <td>0</td> 
   <td>4</td> 
  </tr> 
 </tbody> 
</table>

从下标为1开始的，第一列表示前i个数和为0的情况，只有一种方案。一个都数字都不取；再看第一行表示前0个数字和为j，显然0个数字和为0，多以方案数为0。以此为条件，根据公式，就可以计算出其余的数字了。

>  *  例如：dp\[5\]\[5\] = 3：表示前5个数字中和为5方案数，无非就是两种情况：
>  *  如果不取第5个数字3，那么前4个数字的方案数为dp\[4\]\[5\] = 2；
>  *  如果取第5个数字3，那么剩下的前4个数字需要和为5-3，即dp\[5\]\[2\] = 1；

代码如下：

#include <iostream>
    #include <vector>
    using namespace std;
    int main()
    {
        int n, m;
        cin >> n >> m;
        int size = (m >= n ? m : n) + 1;
        vector<int> arr(size);
        for (int i = 1; i <= n; i++)
            cin >> arr[i];
        vector<vector<long long>> dp;
        dp.resize(size);
        for (int i = 0; i<dp.size(); i++)
            dp[i].resize(size);
    
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = 1;
            for (int j = 0; j <= m; j++)
            {
                if (j < arr[i])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]];
            }
        }
        cout << dp[n][m] << endl;
        return 0;
    }

[01]: https://blog.csdn.net/wei_cheng18/article/details/81192967