JZTXT

多重背包单调队列优化

发布时间 2023-09-30 12:40:34作者: _wbf

引用自：动态规划-背包问题(01背包、完全背包、多重背包)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100005;
int n, m, cnt;
int v[102], num[102], dp[maxn];
struct Queue {
    int pos, val;
}q[maxn];
int main() {
    while (~scanf("%d%d", &n, &m) && n && m) {
        memset(dp, 0, sizeof(dp));
        cnt = 0;
        for (int i = 1; i <= n; i++)scanf("%d", &v[i]);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &num[i]);
            if (v[i] * num[i] >= m) {  //大于背包容量相当于完全背包
                for (int j = v[i]; j <= m; j++)
                    dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
                continue; 
            }                       //单调队列优化
            for (int d = 0; d < v[i]; d++){  //枚举余数
                int head = 1, rear = 0;
                for (int j = 0; j <= (m - d) / v[i]; j++){
                    int cur = dp[j * v[i] + d] - j * v[i];
                    while (head <= rear && q[head].pos < j - num[i]) head++;
                    while (head <= rear && q[rear].val < cur) rear--;
                    q[++rear].val = cur;
                    q[rear].pos = j;
                    dp[j * v[i] + d] = q[head].val + j * v[i];
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++)
            if (dp[i] == i)ans++;
        printf("%d\n", ans);
    }
    return 0;
}