首页 > 其他分享 >【学习笔记】多重背包优化

【学习笔记】多重背包优化

时间:2024-12-23 08:59:20浏览次数:5  
标签:多重 背包 int max 笔记 times tail dp

basic tips

多重背包可以看做 \(\texttt{01}\) 背包和完全背包的结合。

例题:P1776 宝物筛选

这道题完全就是多重背包板子,多重背包就是在 \(\texttt{01}\) 背包与完全背包两者间取了个折中,对于每个体积 \(V_i\),价值 \(W_i\) 的物品多了一个限制,每种物品有且仅有 \(C_i\) 个。

朴素做法

在背包不能装下当前枚举的第 \(i\) 个物品的所有 \(C_i\) 个时,直接转换成完全背包对当前物品进行求解。反之,则转换成 \(\texttt{01}\) 背包,枚举第 \(i\) 个物品的个数。

这样的复杂度即为 \(O(nm\sum{C_i})\),一旦数据稍微大一点就无法接受。

二进制优化

基于倍增思想,举个例子,当我们想拿 \(1024\) 个物品时,我们会去枚举 \(1\) 到 \(1024\),但是若我们 \(1,2,4,8...512,1024\) 这样去拿,最终结果仍然与朴素做法一样,但是仅仅 \(10\) 次就可以得出答案,所以我们是把 \(C_i\) 拆成 \(2^0 + 2^1 + 2^2 + \ldots + 2^{\log_2{C_i} - 1} + x\) 的形式。

所以背包在当前第 \(i\) 个装得下时,我们在枚举个数时直接每次拿 \(2^k\) 个物品去跑 \(\texttt{01}\) 背包,这样的复杂度 \(O(nm\sum\log{C_i})\),可以接受。

code

#include<bits/stdc++.h>
// #define int long long

using namespace std;
const int MAXN = 1e5 + 10;
int n,W,v[MAXN],w[MAXN],m[MAXN],dp[MAXN];
signed main()
{
    scanf("%d %d",&n,&W);
    int ind = 0;
    for(int i = 1;i <= n;i ++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        int ret = 1;
        while(ret <= c)
        {
            v[++ ind] = ret * a;
            w[ind] = ret * b;
            c -= ret;
            ret <<= 1;
        }
        if(c > 0)
        {
            v[++ ind] = c * a;
            w[ind] = c * b;
        }
    }
    for(int i = 1;i <= ind;i ++)
    {
        for(int j = W;j >= w[i];j --)
            dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
    }
    printf("%d\n",dp[W]);
    return 0;
}

单调队列优化

对于转移方程:\(dp_{i,j} = \max\{dp_{i-1,j-k \times v_i} + k \times w_i\}\),所以 \(dp_{i,j-k \times v_i}\) 的值定会被 \(dp_{i,j-(k+1) \times v_i}\) 所影响,举例:

当 \(v_i = 4\),\(j\) 的值如下:\(1,2,3,4,5,6,7,8,9,10,11,12 \dots\)

可以发现 \(1 \equiv 4 (\text{mod } v_i),2 \equiv 5(\text{mod } v_i)\),以此类推。

因此,我们可以根据 \(j\) 对 \(v_i\) 的模数对物品进行分类,所以可以得到 \(j = num + k \times v_i\),其中 \(num\) 为 \(j\) 对 \(v_i\) 的模数,移项得 \(k = \lfloor\frac{j - num}{v_i}\rfloor\),修改转移方程得:\(dp_{j + k \times v_i} = \max\{dp_{j'+ k \times v_i} + (j - j') \times w_i\}\),其中 \(j' \in [\max\{0,j - C_i\},j)\),就可以把 \(\max\) 里那一坨用单调队列优化,复杂度 \(O(nm)\)。

code

#include<bits/stdc++.h>
// #define int long long

using namespace std;
int n,W,v,w,c,q1[100005],q2[100005],head,tail,dp[100005];
signed main()
{
    scanf("%d %d",&n,&W);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d %d %d",&v,&w,&c);
        int tmp = min(c,W / w);
        for(int j = 0;j < w;j ++)
        {
            head = 1,tail = 0;
            int k = (W - j) / w;
            for(int t = 0;t <= k;t ++)
            {
                while(head <= tail && dp[j + t * w] - t * v > q2[tail]) tail --;
                q1[++ tail] = t;
                q2[tail] = dp[j + t * w] - t * v;
                while(q1[head] < t - tmp) head ++;
                dp[j + t * w] = max(dp[j + t * w],q2[head] + t * v);
            }
        }
    }
    printf("%d\n",dp[W]);
    return 0;
}

例题

P1782 旅行商的背包

P1833 樱花

P2760 科技庄园

P7381 [COCI2018-2019#6] Sličice

标签:多重,背包,int,max,笔记,times,tail,dp
From: https://www.cnblogs.com/Ayaka-0928/p/18623003

相关文章

  • 【差分约束】学习笔记
    BasicTips差分约束,即为存在一个差分约束系统,即类似\(x_i-x_j\leqk\)的\(n\)元一次不等式组,求出一组解使得该组内所有不等式全部成立,即\(x_1=s_1,x_2=s_2\dotsx_n=s_n\),否则判无解。对于满足条件的一个解集\(\{s_1,s_2,s_3,\dots,s_n\}\),集合\(\{s_1+t,s_2......
  • 【AI学习笔记4】四种主流的神经网络 FNN、RNN、CNN、Transformer
     一、人工神经网络的分类最常用的人工神经网络(ArtificialNeuralNetwork,ANN)主要包括以下四种:前馈神经网络(FeedforwardNeuralNetwork,FNN)、循环神经网络(RecurrentNeuralNetwork,RNN)和卷积神经网络(ConvolutionalNeuralNetwork,CNN),还有当前最流行的大模型常用的Transformer神......
  • 蓝桥杯——嵌入式学习笔记
    备战2025蓝桥杯嵌入式,记录一下过程。不定期更新,欢迎提出问题和指导。一、cubemx配置    1.芯片选择        嵌入式主板用的是STM32G431RBT系列,因此选择以下芯片    2.Pinout&Configuration        这里调整System......
  • INA226折腾笔记(一)
    其实也算不上折腾,这个模块很简单就一个简单的I2C模块。随便搞个单片机就能读写,之所以玩这个,主要还是对手上的USB表不满意(换句话说就是达不到我的需求)我手上有几个USB表左边那个高仿版FNB58,右边那个是科维斯的CC表型号为KWS-1902C,平时就是测测手机充电功率之类的,也够用,FNB58还带......
  • 8086汇编(16位汇编)学习笔记01.汇编基础和debug使用
    原文链接:https://bpsend.net/thread-100-1-2.html     为什么学习16位汇编?16位操作指令最多能够操作两个字节,且更能够体现出与硬件的交互。16位下的指令和32位汇编的指令差不多。16位汇编的指令在32位一样使用.要学好汇编必须要了解一点点硬件知识,16汇编是直接操作......
  • 【学习笔记】高位前缀和(SOSDP)
    高位前缀和解决这样的问题:给定\(f_i\),其中\(i\in[0,2^n-1]\),求解\(\sum\limits_{j\ini}f_j\)。考虑一维前缀和:for(inti=1;i<=n;i++){ sum[i]=sum[i-1]+a[i];}二位前缀和:for(inti=1;i<=n;i++){ for(intj=1;j<=n;j++){ sum[i][j]=sum[i][j-1]+a[i][j]; }}for......
  • 三维测量与建模笔记 - 7.2 点云滤波
        逐点计算法向量,需要对每一个点拟合出它的切平面,一般使用邻域点信息来查找切平面。    选取要计算的点和它周围一定范围内的点可以拟合出一个平面,最基本的方法是通过最小二乘法取对这些点到平面的距离进行优化(计算量很大)。可以通过计算协方差矩阵来实现......
  • 读书笔记:Redis5设计与源码分析
    Redis5设计与源码分析,陈雷本书赞誉序前言第1章引言11.1Redis简介1Redis由SalvatoreSanfilippo在2009年发布初始版本,开源后不断发展壮大。Redis优点:Redis的工作模式为单线程,不需要线程间的同步操作。Redis采用单线程主要因为其瓶颈在内存和带宽上,而不是CPU。1.2Re......
  • 2024/12月 读书笔记 - 7《构建之法》--- 第七章
    微软解决方案框架(MSF)概述本章将探讨微软公司推荐的软件开发方法——微软解决方案框架(MSF),它融合了多种软件开发方法论和原则,旨在指导微软的软件开发实践。MSF的核心原则开放沟通:确保所有信息透明共享,涉及所有相关角色,并公开决策过程。同时,对敏感信息如技术机密和安全性信息采取......
  • 2024/12月 读书笔记 - 8《构建之法》--- 第八章
    在软件开发过程中,准确捕捉和全面理解用户需求是至关重要的。以下是软件团队获取和处理需求的四个关键步骤:获取和引导需求:也称为“需求捕捉”,软件团队需要站在用户的角度思考,引导用户明确他们的需求。分析和定义需求:对收集到的需求进行整理和定义,从不同角度量化需求。验证需求:与......