多重背包 + 滑动窗口
当前状态取决于前一个状态内取值面值是否为一,这里采用贪心,只要有一个取值为一,就加上该状态
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int n, m;
int f[N], g[N];
int v[N], s[N];
inline void solve()
{
while (scanf("%d%d", &n, &m), n || m)
{
for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
memset(f, 0, sizeof f);
f[0] = 1;
for (int i = 1; i <= n; i ++ )
{
memset(g, 0, sizeof g);
for (int j = v[i]; j <= m; j ++ )
{
if (!f[j] && f[j - v[i]] && g[j - v[i]] < s[i])
{
f[j] = 1;
g[j] = g[j - v[i]] + 1;
}
}
}
int res = 0;
for (int i = 1; i <= m; i ++ ) res += f[i];
cout << res << endl;
}
}
int main()
{
solve();
return 0;
}