首页 > 其他分享 >多重背包单调队列优化

多重背包单调队列优化

时间:2023-09-30 12:44:23浏览次数:34  
标签:多重 背包 队列 int maxn dp include 单调

引用自:动态规划-背包问题(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;
}

标签:多重,背包,队列,int,maxn,dp,include,单调
From: https://www.cnblogs.com/WangBF/p/17737739.html

相关文章

  • 使用链表模拟队列和栈
    使用链表模拟队列案例1//创建节点类publicclassNode{intn;Nodenext;}//编写方法publicclassQueue{Nodehead=newNode();Nodelast=newNode();privateintlen=0;publicintsize(){returnthis.len;}......
  • 使用数组模拟队列和栈
    使用数组模拟队列案例1publicclassQueue{privateint[]num=newint[5];privateintlen=0;publicintsize(){returnthis.len;}//添加publicintadd(intn){if(len<num.length){num[len]=n;......
  • 浅谈数据结构栈与队列
    栈1.栈的基本概念栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。不能插入和删除的一端为栈底(Bottom)栈顶(top):线性表允许进行插入删除的那一端栈底(bottom):固定的,不允许进行插入和删除的那一端空栈:不含任何元素的......
  • 面试之消息队列
    使用mq的优缺点优点解耦,生产者与消费者都只需要与mq进行交互,减少了强依赖。流量削峰,将大量请求放入mq后,服务器可以根据自身能力从mq中拉取消息消费。异步通信,减少客户端响应时间。缺点系统更复杂,运维成本增加。可用性降低,存在mq服务器宕机的风险。 关键角......
  • 延迟队列
    一、延时队列的应用什么是延时队列?顾名思义:首先它要具有队列的特性,再给它附加一个延迟消费队列消息的功能,也就是说可以指定队列中的消息在哪个时间点被消费。延时队列在项目中的应用还是比较多的,尤其像电商类平台:1、订单成功后,在30分钟内没有支付,自动取消订单2、外卖平台发送......
  • 遗传算法解决01背包问题
    遗传算法解决01背包问题一、问题描述01背包问题是组合优化问题的一个典型例子,它要求在许多可行解中找到一个最优解。01背包问题的一般描述如下:给定一个固定的背包容量和一组物品,每个物品有一个重量和一个价值,要求从这组物品中选择一些放入背包,使得背包中物品的总价值最大,同时不......
  • 829. 模拟队列
    829.模拟队列题目链接:829.模拟队列-AcWing题库队列:就是一个特殊的数组。这个数组,最前面叫队头,最后面叫队尾。只允许在最后面添加元素,只允许在最前面删除元素。#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intqu[N];intmain(){int......
  • 在sqlserver2008中使用自带的消息队列Service Broker
    以前有个业务操作本来是用sqlserver的表中触发器来处理的,后来在使用一个存储过程中,涉及到这个表后,发现存储过程执行过程,需要等待涉及的表的触发器操作完成才会返回,导致这个存储过程耗时有点久,这样就出现锁的问题,本来想改造下代码写到C#中,后来也懒得弄了,就找了找,发现可以用消息队......
  • 225. 用队列实现栈
    请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。实现 MyStack 类:voidpush(intx) 将元素x压入栈顶。intpop() 移除并返回栈顶元素。inttop() 返回栈顶元素。booleanempty() 如果栈是空的,返回 true ;否则,返回 fals......
  • 【算法】栈与队列
    1栈与队列理论基础队列先进先出,栈先进后出;不允许有遍历行为,不提供迭代器2用栈实现队列题目:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现 MyQueue 类:voidpush(intx) 将元素x推到队列的末尾intpop() 从队列......