01背包求方案数

$ 时间复杂度O(NM),空间复杂度O(M) $
空间为M是因为优化成一维

一般求背包方案数都需要手动初始化

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 110, M = 1e4 + 10;

int f[M], a[N];
int n, m;

int main(){
    //读入
    cin >> n >> m;
    for (int i = 0 ; i < n ; i ++) cin >> a[i];

    //DP
    f[0] = 1;//初始化
    for (int i = 0 ; i < n ; i ++){
        for (int j = m ; j >= a[i]; j --){
            f[j] += f[j - a[i]];
        }
    }

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