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

多重背包 单调队列优化

时间:2024-06-13 16:55:09浏览次数:30  
标签:www 背包 队列 int hh 物品 include 单调

https://www.acwing.com/problem/content/6/

#include <iostream>
#include <memory.h>
#include <deque>
#include <stdio.h>

using  namespace std;

/*
https://www.acwing.com/problem/content/6/


有 N种物品和一个容量是 V的背包。
第 i种物品最多有 si件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式
第一行两个整数,N,V (0<N≤1000, 0<V≤20000)
,用空格隔开,分别表示物品种数和背包容积。

接下来有 N行,每行三个整数 vi,wi,si
,用空格隔开,分别表示第 i种物品的体积、价值和数量。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N≤1000

0<V≤20000

0<vi,wi,si≤20000
提示
本题考查多重背包的单调队列优化方法。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
*/

const int N = 20010;
int g[N], f[N];
int q[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        //f[]是当前dp  g[]是上一次dp ,体积是索引
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j++) {
            int hh = 0; int tt = -1;
            for (int k = j; k <= m; k += v) {
                //本次的体积k 取s个物品 那么 最多需要f[k-s*v]的数据 比k-s*v小的体积 弹出队列
                while (hh <= tt && k - s * v > q[hh]) hh++;
                //得到f[k]的最大值
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                //排除无需在比较的体积v  为啥减去额外的w?
                //自己做了修改 q[tt]和k在相同情况下比较决定是否弹出。 补上了两者v相差的额外w
                while (hh <= tt && g[q[tt]] + (k- q[tt] ) / v * w < g[k]  ) tt--;
                q[++tt] = k;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

我的视频题解空间

标签:www,背包,队列,int,hh,物品,include,单调
From: https://www.cnblogs.com/itdef/p/18246252

相关文章

  • 云消息队列 ApsaraMQ 成本治理实践(文末附好礼)
    作者:家泽、稚柳前言:在AI原生应用架构浪潮中,消息队列需支持大规模数据和复杂AI模型训练与推理场景下的高效异步通信,其成本效益优化也日益受到重视。面对大模型或大数据量,消息量显著增加,云消息队列ApsaraMQ致力于降低消息队列成本,减轻用户负担,同时,通过架构演进,提升数据处理......
  • c++ 实现优先队列
    优先队列底层是堆,下面给出大根堆代码Push是在新节点到根节点的路径上寻找合适的插入位置;Pop是删除根节点之后维护大根堆,顺便为最后一个元素寻找合适的位置;1#include<bits/stdc++.h>23usingnamespacestd;45template<classT>6classp_queue{7pri......
  • 代码随想录算法训练营第10天 | 队列和栈基础知识、225用队列实现栈、用栈实现队列
    232用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/用栈实现队列代码随想录https://programmercarl.com/0232.用栈实现队列.html#其他语言版本225用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/description/用队列实现......
  • 【背包问题】基于matlab混合遗传算法求解背包问题(目标函数:总重 总价值)【含Matlab源码
    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。......
  • DP经典问题----背包问题的代码实现(入门级)(C++/PYTHON)
    背包的状态转换方程i:表示物品序号j:表示背包大小W[i]:表示第i件物品的重量f[i,j]:表示在前i件物品中选择若干件放在承重为j的背包中,可以取得的最大价值f[i-1,j-Wi]:表示在前i-1件物品中选择若干件放在承重为j-Wi的背包中,可以取得的最大价值Pi(j>=Wi):表示第i件物品的价值,要......
  • (nice!!!)LeetCode 2865. 美丽塔 I(数组、单调栈)
    2865.美丽塔I思路:方法一,时间复杂度0(n^2)。枚举每一个点i作为当前山脉数组的最高点。然后我们通过预处理遍历其前面和后面,来更新两个数组f1、f2。数组f1[i]:表示在满足非递减的情况下,区间0~i,以点i的高度heighs[i]为最高点所能形成的最大高度和。数组f2[i]:表示在满足非......
  • 代码随想录算法训练营第三十六天 | 406.根据身高重建队列
    406.根据身高重建队列题目链接文章讲解视频讲解思路:  先按照身高由大到小排序,如果身高相同,比较人数(由小到大);  按照人数重构数组,将节点插入到合适的位置classSolution{private:staticboolcompareByK(vector<int>&lhs,vector<int>&rhs){if(lhs[......
  • 队列结构认识
    目录什么是队列?消息处理的触发机制异步消息队列的概念常见的异步消息队列框架什么是队列?队列数据结构的特点:跟排队一样:先进先出。队列的应用场景:一般在业务中,常常把队列作为一种中间件服务,比如当要处理大量消息的时候,往往是把这些消息放入一个队列存储,这时并不需要立即对它......
  • IO进程线程(十一)进程间通信 消息队列
    文章目录一、IPC(Inter-ProcessCommunication)进程间通信相关命令:(一)ipcs---查看IPC对象(二)获取IPC键值(三)删除IPC对象的命令(四)获取IPC键值的函数1.函数定义2.使用示例二、消息队列(一)特点(二)相关API1.创建或获取一个消息队列2.向消息队列中写消息3.在消息队列中......
  • 二分#背包#快排#LCS详解
    二分#背包#快排#LCS详解文章目录二分#背包#快排#LCS详解1.二分搜索2.01背包问题3.快速排序4.最长公共子序列1.二分搜索在处理大规模数据集时,查找操作的效率显得尤为重要。二分搜索是一种在有序数组中查找目标值的高效算法,其时间复杂度为O(logn)。二分搜索通......