算法

(贪心) $O(nm)$

可以当作多重背包来做。
但是因为这里只是问是否存在方案。
如果不行可以一个个试，不用枚举 $c[i]$ 次。
这样时间复杂度就是 $O(nm)$

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;

const int N = 110;
const int M = 100100;

int v[N], c[N];
int f[M], sum[M]; // f[i] 表示是否能拼出i，sum[j] 表示为了能拼出j需要用几个v[i] 

int main() {
    int n, m;

    while (cin >> n >> m, m) {
        for (int i = 1; i <= n; ++i) cin >> v[i];
        for (int i = 1; i <= n; ++i) cin >> c[i];
        std::memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            std::memset(sum, 0, sizeof sum);
            for (int j = v[i]; j <= m; ++j) {
                if (!f[j] and f[j - v[i]] and sum[j - v[i]] < c[i])
                    f[j] = 1, sum[j] = sum[j - v[i]] + 1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            if (f[i]) ++ans;
        }
        cout << ans << '\n';
    } 

    return 0;
}