首页 > 其他分享 >背包DP

背包DP

时间:2023-01-28 23:13:31浏览次数:35  
标签:背包 int leq DP 物品 dp bitset

背包dp

前言 :由于普通的背包板子太板了,所以不多赘述,直接讲有价值的

1.多重背包的二进制优化

把一个物品的数量二进制拆分,例如有10个价值a的物品,我们把它拆成1+2+4+3个,这样保证可以用这4个物品凑出想要的解 代码很妙

 int k=1,c=物品数量,v=物品价值,cnt,a[];
 while(k<=c){
     a[++cnt]=v*k;
     c-=k;
     k*=2;
 }
 if(c!=0){
     a[++cnt]=c*v;
 }

2.01背包和完全背包的滚动数组

 //01背包
 for(int i=1;i<=n;i++){
     for(int j=m;j>=w[i];j--){
         dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    }
 }
 //完全背包
 for(int i=1;i<=n;i++){
     for(int j=w[i];j<=m;j++){
         dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    }
 }

发现在枚举j的时候顺序变了,为什么呢

01背包 dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-w[i]}+c[i])

所以滚动时,dp_{j}还没有被当前的i更新,所以dp_{j}表示上一层的dp_j

而完全背包 dp_{i,j}=max(dp_{i-1,j},dp_{i,j-w[i]}+c[i])

dp_j需要已经更新过的dp_j所以正着来

3.一道很有启发的题目

有价值1,2,3,4,5,6,7,8的物品个a_i件,最大能凑成的小于m的数(1\leq m \leq 1e18)

其实没什么思路,讲解后看了题解才搞懂

我们令d=gcd(1,2,3,4,5,6,7,8)=840

 

第一步:我们用其中一种价值的物品去凑d

若最后的答案为ans ans=k\times d+c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8

c为凑完d后每种物品剩下的价值

如果c_i要大于d的话,我们可以在c_i提取一个d出来,所以最后其中任意一个的c_i是小于d的

你会发现,c_i的大小决定了前面可以凑出多少个d,所以这就是一个背包问题,c_i的和为背包容量,我们需要合理分配c_i的大小来保证能前面能选取更多的d

应为每个c都小于d,多以8个c会一定小于8\times d,这就是背包容量的最大值 dp_{i,j}表示前i个物品,c_i的和刚好为j时(即把d凑完后剩下的和),能组成多少个d,也就是式子里面的k

最后枚举c的和,然后计算答案

4.特殊数据的01背包

1.m\leq 1e9 \quad n\leq 100 \quad c\leq1000

把状态反过来,dp_{i,j}表示前i个物品获得价值为j时的最小重量

2.m\leq 2e5 \quad n\leq 2e5 \quad w\leq100

发现重量很小,所以每两个重量的差也会很小,所以当m比较大时,我们可以按照性价比排序选择,若当前剩余的m很大了,也就是说无论如何m短时间内都不会被选满,所以对背包影响可以忽略

但是当m很小的时候,我们每个物品就显得很重要了,这时我们用背包dp

5.bitset优化背包

bitset就是一个自定义长度,空间小,速度快的01序列 可以像二进制一样进行左移、右移、与、或、非、异或等操作

例如状态转移方程dp_{i,j}|=dp_{i-1,j-w}

此时我们就可以把dp_i这一整行定义为一个bitset,让他去或上dp_j这一行的bitset左移w位的bitset 左移w位,就相当于这个bitset的每一位都向前挪了t步,就相当于每一位下标减小了t

 



标签:背包,int,leq,DP,物品,dp,bitset
From: https://www.cnblogs.com/laozhuma/p/17071465.html

相关文章

  • AcWing 01背包问题
    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总......
  • 什么是DPT中的Odd Cycle问题?它会有什么问题?该如何解决?
    什么是DPT中的OddCycle问题?它会有什么问题?该如何解决?本文选自知识星球中的ICC2教程,更多IC干货见星球,同时星球QQ群还有分享高达40多万字的个人数字后端设计笔记,欢迎加入,......
  • 对 sosdp 的一些理解
    sosdp可以做的题目:对子集/超集的dp,这里对子集相关的部分做一下分析参考资料设\(f[mask][i]\)表示从低到高考虑到\(mask\)的第\(i\)位(从0开始算),而且这\(i+1\)......
  • 【面试高频题】难度 3.5/5,综合最短路的 DP 问题
    题目描述这是LeetCode上的​​1976.到达目的地的方案数​​,难度为中等。Tag:「最短路」、「拓扑排序」、「动态规划」你在一个城市里,城市由 个路口组成,路口编号为......
  • 算法_dp
    2023牛客寒假算法基础集训营1B题四维dp+前缀和处理题目描述众所周知,2022年是四年一度的世界杯年,那么当然要整点足球题。本题需要你模拟一支队伍的一赛季联赛征程。联......
  • 状压 DP(ZR)
    [PKUSC2018]最大前缀和从部分分出发考察性质,“满足a中至多一个负数”怎么做?好吧这个很简单,但是它提醒我们从负数的POV考虑。不难发现,最大前缀和的结束为止一定是某个......
  • 数位 DP
    概述数位DP是以从数学意义上的位数出发来DP为特点的一类DP。下述特点中的一部分可能对计数类以外的不适用。状态设计通常包含“考虑到第几位”和“是否已经......
  • P5858 「SWTR-03」Golden Sword DP+单调队列模板
    P5858「SWTR-03」GoldenSword-洛谷|计算机科学教育新生态(luogu.com.cn) 理解题意后,我们知道贪心和暴力枚举显然是不行的,联想到DP我们设置dp[i][j]表示,第i种......
  • LeetCode正则表达式匹配(lambda/dp)
    lambda表达式[捕获列表](参数列表)mutable(可选)异常属性->返回类型{//函数体}所谓捕获列表,其实可以理解为参数的一种类型,lambda表达式内部函数体在默认情况下......
  • 动态规划 背包问题算法模板
    一篇文章吃透背包问题!(细致引入+解题模板+例题分析+代码呈现)  https://leetcode.cn/problems/partition-equal-subset-sum/solution/yi-pian-wen-zhang-chi-tou-bei-b......