概览

输入N个正整数, 从中选出若干个数，使它们的和等于M。求有多少种选择方案。

题解

01背包问题，从n个物品中选择，每个物品有体积和价值，在满足体积的条件下，使得
f[i,j]
从前i个数中选择，恰好为j的选法的数量

第i个数不选 f[i,j] = f[i-1,j]
第i个数选 f[i,j] = f[i-1, j-s]

问题是数量又该如何进行更新呢？
两个集合不需要并在一起，所以直接进行数量相加即可

注意！如果这样用二维就错了！这里集合划分是下面的
f[i,j] = sum(f[0][j], f[1][j], .. f[i-1][j]) + sum(f[0][j-s], f[1][j-s], …f[i-1][j-s])
f[i-1,j] = sum(f[0][j], f[1][j], …f[i-2][j]) + sum(f[0][j-s], f[1][j-s], … f[i-2][j-s])

所以实际上用一维来做才是正确的! 注意!
这里前i个是没有顺序性的!

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int f[N];

int main() {
    cin >> n >> m;

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

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

}