算法1:(暴力枚举) $O(n)$
//多重背包求方案数
//f[j]表示数量不超过j所能摆放的方案数
#include <bits/stdc++.h>
using namespace std;
const int N = 110, MOD = 1000007;
int f[N], n, m;
int main() {
cin >> n >> m;
f[0] = 1; //0个花盆也是一种方案
for (int i = 1, a; i <= n; ++ i) { //物品
cin >> a; //读入多重背包的数量
for (int j = m; j >= 1; -- j) //体积
for (int k = 1; k <= a && j >= k; ++ k) //决策,选择k个物品j,不选就是上一次的状态 不用从0开始循环
f[j] = (f[j] + f[j-k]) % MOD;
}
cout << f[m];
return 0;
}