题目描述

blablabla

样例

blablabla

算法1

01背包模型 时间：$O(n^2)$，空间：$O(n)$

采用01背包模型。
状态表示：$f(i,j)$表示从前$i$个数字中选，数字总和恰好为$j$的方案数。

集合划分：集合划分为不取第$i$个数字和取第$i$个数字两种。前者对应的状态表示为$f(i-1,j)$（即从前$i-1$个数字中选，数字总和恰好为$j$的方案数）；后者对应的状态表示为$f(i-1,j-a[i])$（即从前$i-1$个数字中选，数字总和恰好为$j-v[i]$的方案数，再加上$i$的大小，数字总和恰好为$j$）。那么，数字总和恰好为$j$的方案数是两者之和。

因此，状态转移方程：$f(i,j) = f(i-1,j) + f(i-1,j-a[i])$

状态初始化：从状态的定义出发，不考虑任何物品的时候，数字总和为零，因此“考虑前$0$个物品，体积恰好为$0$的方案数为1“，即$f(0,0) = 1$；反之，$f(0,j) = 0, j > 0$。

空间上同样可以节省1维，因此最终的方程是：
$f(j) = f(j) + f(j-a[i])$

时间复杂度

状态数$O(n^2)$，状态计算复杂度是$O(1)$，因此整体复杂度是$O(n^2)$。

参考文献

C++ 代码

#include <iostream>

using namespace std;

const int N = 110, M = 10010;
int f[M];
int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    f[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= a[i]; j--) {
            f[j] += f[j - a[i]];
        }
    }

    cout << f[m] << endl;
    return 0;
}