题目描述

blablabla

样例

blablabla

算法1

完全背包问题求方案数 时间：$O(n^2)$，空间$O(n)$

该题属于完全背包问题求方案数问题。

首先定义状态表示：$f(i,j)$表示仅从前$i$本书中选，总花费恰好为$j$的方案数。

集合划分：依靠最后一个物品$i$选多少个，可以划分成若干个子集，这些子集对应的状态表示如下：
不选$i$：$f(i-1,j)$
选1个$i$：$f(i-1,j-v[i])$
选2个$i$：$f(i-1,j-v[i] \times 2)$
…
选k个$i$：$f(i-1,j-v[i] \times k)$

状态转移方程为上述子集的求和：
$f(i,j) = f(i-1,j) + f(i-1,j-v[i]) + f(i-1,j-v[i] \times 2) + … + f(i-1,j-v[i] \times k)$

如果使用上述状态转移方程求解状态$f(i,j)$，那么状态转移的计算量是$O(n)$的。我们可以对其进行优化。

观察状态$f(i,j-v[i])$的状态转移方程：
$f(i,j-v[i]) = f(i-1,j-v[i]) + f(i-1,j-v[i] \times 2) + … + f(i-1,j-v[i] \times k)$

可以看出，$f(i,j-v[i])$的状态转移方程的展开式与$f(i,j)$的状态转移方程的第二项到最后一项完全一致。因此，我们可以用$f(i,j-v[i])$替而代之。

优化后的状态转移方程是：
$f(i,j) = f(i-1,j) + f(i-1,j-v[i])$

优化后的状态计算复杂度是$O(1)$。

同样，参考完全背包问题，可以对空间进行优化:
$f(j) = f(j) + f(j-v[i])$
其中，$j$从小到大进行遍历。

状态初始化：从状态定义出发，从第0个物品中选，花费恰好是0的方案数是1，因此：
$$ f(j) = \begin{cases} 1, j = 0\\\ 0, j > 0\\\ \end{cases} $$

时间复杂度

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

参考文献

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010;

int f[N];
int v[4] = { 10, 20, 50, 100 };

int main()
{
    int n; 
    cin >> n;
    f[0] = 1;
    for (int i = 0; i < 4; i++) {
        for (int j = v[i]; j <= n; j++) {
            f[j] += f[j-v[i]];
        }
    }

    cout << f[n] << endl;

    return 0;
}