背包基础

发布时间：2026/7/25 11:51:59

背包基础

观前提醒：你需要一个AcWing账号。

一.01背包

算是最最简单的背包了。

例题1：洛谷P1048&AcWingT2

给你\(n\)个物品和一个背包，该背包的最大容积是\(V\)。

对于第\(i\)个物品，它有自己的体积\(v_i\)和价值\(w_i\)。

你要选一些物品放入背包，使得物品的体积之和不超过最大容积\(V\)，且价值之和最大。输出最大价值之和。

因为每种物品只有一个，选了可以看作1，没选就是0，所以它叫01背包。

非常经典的背包dp题目对吧。

我们令\(dp_{i,j}\)表示考虑前\(i\)个物品选法，最大容量为\(j\)时的最大价值之和。那么\(dp_{n,V}\)显然就是答案。

接下来考虑转移方程。对于第\(i\)样物品，无非就是选或不选两种情况。

如果不选最优（或者说\(j\)小于\(v_i\)所以选不了\(i\)），那么就是考虑前\(i-1\)个物品在最大容量为\(j\)时的选法，即\(dp_{i,j}=dp_{i-1,j}\)。

如果\(j\)大于\(v_i\)且选\(i\)更优，那么就是在前\(i-1\)个物品里先选着，然后再把\(i\)选上，体积之和不超\(j\)。

所以前\(i-1\)个物品的体积之和应该限制在\(j-v_i\)内，也就是\(dp_{i,j}=dp_{i-1,j-v_i}+w_i\)。

到这里，我们的转移方程就写出来了：

\[ dp_{i,j}=\begin{cases}dp_{i-1,j} & (j<v_i) \\max(dp_{i-1,j},dp_{i-1,j-v_i}+w_i) & (j>=v_i) \\\end{cases} \]

显然，时间复杂度是\(O(nV)\)，空间复杂度也是\(O(nV)\)的。

至此我们最朴素的01背包代码诞生了：

二维dp数组代码 
#include<iostream>
using namespace std;
int V,n,v[110],w[110],dp[110][1010];
int main(){cin>>V>>n;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j-v[i]>=0){dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);}else{dp[i][j]=dp[i-1][j];}}}cout<<dp[n][V];return 0;
}

当然，注意到\(i\)的dp值（不论容积是多少）只与\(i-1\)有关，我们还可以用滚动数组优化掉第一维，就像这样。

滚动数组代码 
#include<iostream>
using namespace std;
int V,n,v[110],w[110],dp[2][1010];
int main(){cin>>V>>n;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}//x&1就是x%2的意思，也就是取除以二的余数 for(int i=1;i<=n;i++){for(int j=0;j<=V;j++){if(j-v[i]>=0){dp[i&1][j]=max(dp[(i-1)&1][j],dp[(i-1)&1][j-v[i]]+w[i]);}else{dp[i&1][j]=dp[(i-1)&1][j];}}}cout<<dp[n&1][V];return 0;
}

但是更常见的写法还是下面这一种，把第一维彻底滚掉：

我们画一个图就会发现，如果把dp数组看成一个方格图，那么根据上面的转移方程，\(dp_{i,j}\)一定从自己正上方，或者是左上方转移而来：

\(\begin{bmatrix}dp_{1,1} & dp_{1.2} & dp_{1,3} & \cdots & dp_{1,j-v_i} & \cdots & dp_{1,j} & \cdots & dp_{1,V} \\dp_{2,1} & dp_{2.2} & dp_{2,3} & \cdots & dp_{2,j-v_i} & \cdots & dp_{2,j} & \cdots & dp_{2,V} \\\vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\dp_{i-1,1} & dp_{i-1.2} & dp_{i-1,3} & \cdots & dp_{i-1,j-v_i} & \cdots & dp_{i-1,j} & \cdots & dp_{i-1,V} \\dp_{i,1} & dp_{i.2} & dp_{i,3} & \cdots & dp_{i,j-v_i} & \cdots & dp_{i,j} & \cdots & dp_{i,V} \\\vdots & \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\dp_{n,1} & dp_{n.2} & dp_{n,3} & \cdots & dp_{n,j-v_i} & \cdots & dp_{n,j} & \cdots & dp_{n,V} \\\end{bmatrix} \)

由此我们想到：如果把表示物品\(i\)的那一维压缩掉，只保留最大容量\(j\)那一维，且倒序枚举最大容量\(j\)，那么在更新\(dp_j\)的时候，用到的就是\(dp_j\)和\(dp_{j-v_i}\)，存的都是\(i-1\)时的dp值。由此转移方程就变成了：

\[ dp_{j}=\begin{cases}dp_{j} & (j<v_i) \\max(dp_{j},dp_{j-v_i}+w_i) & (j>=v_i) \\\end{cases} \]

这样我们又能进行一个小优化：\(j\)只需要从\(v_i\)~\(V\)枚举，因为显然\(j<v_i\)时dp值就是它本身。

代码：

一维dp代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){//快读int x=0;char c=getchar();while(c<48) c=getchar();while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}const int N=1314;
const int WT=1314;
int n,V,v[N],w[N],dp[WT]; signed main(){n=read(),V=read();for(int i=1;i<=n;i++){v[i]=read(),w[i]=read();}for(int i=1;i<=n;i++){for(int j=V;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}printf("%lld",dp[V]);return 0;
}

例题2：洛谷P1164&AcWingT11

顺着刚才求最优方案的思路，我们同样可以做背包计数类问题。

先说AcWing的T11。我们考虑在dp数组之外另建一个cnt数组，\(cnt_{i,j}\)表示考虑前\(i\)个物品，最大容量为\(j\)（体积之和不超过\(j\)）时的合法方案数。

根据dp的转移方程，如果\(j<v_i\)，那么显然方案只有不选\(i\)一种，\(cnt_{i,j}=cnt_{i-1,j}\)。

如果\(j>=v_i\)，那么就比较\(dp_{i-1,j}\)和\(dp_{i-1,j-v_i}+w_i\)的大小，谁大就让\(dp_{i,j}\)等于谁。

对于\(cnt_{i,j}\)，先考虑一种最特殊的情况：\(dp_{i-1,j}=dp_{i-1,j-v_i}+w_i\)。此时不论选不选\(i\)，都能选到当前最优价值。根据加法原理，显然\(cnt_{i,j}=cnt_{i-1,j}+cnt_{i-1,i-v_i}\)。

否则，如果\(dp_{i-1,j}>dp_{i-1,j-v_i}+w_i\)，那么说明不选\(i\)为最优解，\(cnt_{i,j}=cnt_{i-1,j}\)；反之选\(i\)为最优解，\(cnt_{i,j}=cnt_{i-1,j-v_i}\)。

代码（AcWingT11）：

AcWingT11代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; 
}const int N=1314;
const int WT=1314;
const int mod=1e9+7;
int n,V,dp[N][N],cnt[N][N];signed main(){n=read(),V=read();//没有容量或0号物品时无法选物品，也是一种最优方案，记得初始化为1for(int i=1;i<=n;i++){cnt[i][0]=1;}for(int i=0;i<=V;i++){cnt[0][i]=1;}for(int i=1;i<=n;i++){int v=read(),w=read();for(int j=1;j<=V;j++){if(j<v){dp[i][j]=dp[i-1][j];cnt[i][j]=cnt[i-1][j];}else{if(dp[i-1][j]>dp[i-1][j-v]+w){cnt[i][j]=cnt[i-1][j];}else if(dp[i-1][j]==dp[i-1][j-v]+w){cnt[i][j]=(cnt[i-1][j]+cnt[i-1][j-v])%mod;}else{cnt[i][j]=cnt[i-1][j-v];}dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w);}}}printf("%lld\n",cnt[n][V]);return 0;
}

再说P1164。我们定义\(g_{i,j}\)为考虑前\(i\)个物品，体积之和恰好为\(j\)的方案数，显然答案为\(g_{n,V}\)。

这样一来转移方程呼之欲出：当\(j<v_i\)时，无法选\(i\)号物品，显然只能考虑前\(i-1\)个物品恰好填满\(j\)的方案，\(g_{i,j}=g_{i-1,j}\)。

如果\(j>=v_i\)，那么一方面可以是不选\(i\)，让\(i-1\)个物品填满\(j\)；另一方面可以选\(i\)，让其余\(i-1\)个物品体积之和为\(j-v_i\)，此时\(g_{i,j}=g_{i-1,j}+g_{i-1,j-v_i}\)。

代码：

洛谷P1164代码 
#include<iostream>
using namespace std;
int n,V,v[520],g[110][10010];
int main(){cin>>n>>V;for(int i=1;i<=n;i++) cin>>v[i];for(int i=0;i<=n;i++) g[i][0]=1;//无法装东西时容积为0，j=0时也是一种方案 for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j-v[i]>=0) g[i][j]=g[i-1][j]+g[i-1][j-v[i]];else g[i][j]=g[i-1][j];}}cout<<g[n][V];return 0;
}

例题3.AcWingT12

01背包输出字典序最小的方案类问题。

无疑1号物品是n个物品里面编号最小的一个。如果选1号物品能使方案最优的话肯定选1号物品，否则再去2~n里选择物品。

由此我们定义\(dp_{i,j}\)表示考虑i ~ n里的物品，最大容量是\(j\)时的最优解。由于物品的顺序并不重要，它的转移方程跟普通的01背包类似，为：

\[ dp_{i,j}=\begin{cases}dp_{i+1,j} & (j<v_i) \\max(dp_{i+1,j},dp_{i+1,j-v_i}+w_i) & (j>=v_i) \\\end{cases} \]

倒序算dp有一个好处，当我们顺序考虑到第\(i\)个物品时，因为1 ~ i-1已经考虑完了，此时\(i\)已经是最小的数字了。

这样，如果\(dp_{i,j}=dp_{i-1,j-v_i}\)，说明选上\(i\)有最优方案，不论\(dp_{i,j}\)是否还等于\(dp_{i-1,j}\)，即不选i也有最优方案。因为\(i\)是最小的一个了，所以我们要尽可能的选上\(i\)。否则说明不选\(i\)更优，就不输出\(i\)。

注意。选完\(i\)后最大容量会扣掉一个\(v_i\)。

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1314;
const int WT=1314;
int n,V,v[N],w[N],dp[N][N];signed main(){n=read(),V=read();for(int i=1;i<=n;i++){v[i]=read(),w[i]=read();}//普通01背包dp for(int i=n;i>=1;i--){for(int j=0;j<=V;j++){dp[i][j]=dp[i+1][j];if(j>=v[i]){dp[i][j]=max(dp[i][j],dp[i+1][j-v[i]]+w[i]);}}}int cur=V;//统计答案 for(int i=1;i<=n;i++){if(i==n&&cur>=v[n]){//判断边界 printf("%lld",i);return 0;}if(cur<=0) return 0;//此时没法选中新的物品，直接结束循环 if(cur>=v[i]&&dp[i][cur]==dp[i+1][cur-v[i]]+w[i]){printf("%lld ",i);cur-=v[i];//输出并减小剩余容量 }}return 0;
}

例题4.二维费用背包 AcWingT8

无非是又增加了一个限制条件。还是走01背包的思路，考虑第\(i\)种物品选或不选（同样，选的话要满足限制条件），易得转移方程如下：

\[ dp_{i,j}=\begin{cases}dp_{i-1,j} & (j<v_i) \\max(dp_{i-1,j},dp_{i-1,j-v_i}+w_i) & (j>=v_i) \\\end{cases} \]

二.完全背包

例题.洛谷P1616&AcWingT3

与01背包不同的是，完全背包的物体有无限个。

我们还是可以沿用01背包设计的状态，设\(dp_{i,j}\)为考虑前\(i\)个物品，最大容积为\(j\)时的最大价值和。

这样我们沿用01背包的思路，第\(i\)种物品可以不选、可以只选一个、可以选两个……直到容积超了为止。

这样朴素的转移方程就是\(dp_{i,j}=\max\limits_{k=0}^{k*v_i<=j}dp_{i-1,j-k*v_i}+k*w_i\)。

但是这也太慢了……所以我们肯定要考虑优化。

如果感性理解的话，每种物品都有两种情况：要么一个不放，要么放至少一个。如果是一个不放，那就同01背包，\(dp_{i,j}=dp_{i-1,j}\)。如果放多个呢，那么就是在原来\(i\)可能放了好几个的基础上再放一个，\(dp_{i,j}=dp_{i,j-v_i}+w_i\)（注意下标和01背包的不同）。因为我们这里要考虑\(i\)物品已经有一部分在包里的情况。当然，此时最大容积\(j\)必须大于等于\(v_i\)（否则显然放不开吧……）

那么我们的转移方程就是：

\[ dp_{i.j}=\begin{cases}dp_{i-1,j} & (j<v_i) \\max(dp_{i-1,j},dp_{i,j-v_i}+w_i) & (j>=v_i) \\\end{cases} \]

有人可能觉得这太感性了，那接下来我们理性证明一下：

以下是最原始的转移方程递推出来的式子，为了好看我们对一下齐：

dp[i][j] = max( dp[i-1][j] , dp[i-1][j-v[i]]+w[i] , dp[i-1][j-2v[i]]+2w[i] , dp[i-1][j-3v[i]]+3w[i] , .....)
dp[i][j-v[i]]=max( dp[i-1][j-v[i]] , dp[i-1][j-2v[i]] + w[i] , dp[i-1][j-3v[i]]+2*w[i] , .....)

发现没有？\(dp_{i,j}\)取的其实就是\(dp_{i-1,j}\)和\(dp_{i,j-v_i}+w_i\)的最大值，完美符合我们的转移方程式。

于是最最朴素的代码有了：

二维dp 
#include<iostream>
using namespace std;
int V,n,v[1010],w[1010],dp[1010][1010];
int main(){cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j-v[i]>=0){dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);}else{dp[i][j]=dp[i-1][j];}}}cout<<dp[n][V];return 0;
}

当然呢，同01背包，我们也可以把dp数组优化成滚动数组和一维数组。

滚动数组优化无非是将第一维时刻%2，没什么好说的。重点说说如何压缩成一维数组。

其实也很简单，逻辑和01背包极其类似，不同点是，这里我们用的是第\(i\)层的\(j-v_i\)，所以我们改成将\(j\)正向枚举，这样用到的\(dp_{j-v_i}\)就是第\(i\)轮更新过的了。

代码：

一维dp 
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0;char c=getchar();while(c<48) c=getchar();while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}const int N=1314;
const int WT=1314;
int n,V,v[N],w[N],dp[WT]; signed main(){n=read(),V=read();for(int i=1;i<=n;i++){v[i]=read(),w[i]=read();}for(int i=1;i<=n;i++){for(int j=v[i];j<=V;j++){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}printf("%lld",dp[V]);return 0;
}

三.多重背包

例题1：AcWingT4

和前两个背包都不同的是，每个物品都不止只有一个，也不是无穷个，而是一个给我们的特定的数量。

首先最朴素的想法是：当01背包做，把多个同种物品拆开，当成多个只有一件的不同物品。然后这个题就AC了。

时间复杂度\(O(nm \times s_{max})\)。

T4代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0;char c=getchar();while(c<48) c=getchar();while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}const int N=123;
int n,V,v[N*N],w[N*N],dp[N*N],tot;signed main(){n=read(),V=read();for(int i=1;i<=n;i++){int x=read(),y=read(),z=read();while(z--){//这里是拆分物品 tot++;v[tot]=x;w[tot]=y;}}for(int i=1;i<=tot;i++){for(int j=V;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}printf("%lld",dp[V]);return 0;
}

然鹅这也太慢了……如果数据再大点就过不了了。

我们重新思考一下。我们这么做的目的是什么？是确保\(i\)号物品选择\(0 - s_i\)的所有情况都被考虑到。那如果能换一种拆分数目更少的、而且能通过多个物品相加表示出\(0 - s_i\)中所有数字的方式就好了。可是真的有这种方式吗？

当然了。我们按照二进制拆分一下，将第\(i\)样物品的个数\(s_i\)拆成1、2、4、8……直到剩余的数已经不满下一个2的次方了，那就把这部分单独留下就行了。

比如，18按照这个拆法，就应该是1、2、4、8、3（因为1+2+4+8=15，下一个次方是16，18此时剩3，不够了，3就单出来了）。

要证明也很简单，不考虑最后剩的数字，假设前面的数到了\(2^x\)次方，物品总个数为\(num\)，那么根据二进制，每一个2的次方就相当于控制某一位上的数字。选是1，不选是0。

比如，选择1、2、8，对应到二进制上就是1011，也就是11。这样易得，\([0,2^{x+1}-1]\)内的数都能表示出来。这是不考虑剩余的那个数（即\(num-2^{x+1}+1\))能表示出来的数。

那么考虑了这个数呢？那就是\([num-2^{x+1}+1,num]\)呗。由于\(num-2^{x+1}+1<2^{x+1}\)（否则能凑出来下一个幂次\(2^{x+1}\))，所以\(num-2^{x+1}+1<=2^{x+1}-1\)，所以两个区间一定能完全把\([0,num]\)区间里的整数囊括在内。

至此我们就证明了这个方法的可行性。显然，这样做，时间复杂度是\(O(nmlogs)\)的，比刚才快了不少。（因为会有\(nlogs\)件物品）。

代码：

T5代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0;char c=getchar();while(c<48) c=getchar();while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}const int N=123;
int n,V,v[N*N],w[N*N],dp[N*N],tot;signed main(){n=read(),V=read();for(int i=1;i<=n;i++){int x=read(),y=read(),z=read();int qwq;for(qwq=1;qwq<=z;z-=qwq,qwq*=2){//拆分过程同解析 v[++tot]=x*qwq;w[tot]=y*qwq;}if(z){//剩余部分单独装起来 v[++tot]=x*z;w[tot]=y*z;}}//拆分完就是普通01背包啦，注意物品已经不是n件了 for(int i=1;i<=tot;i++){for(int j=V;j>=v[i];j--){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}printf("%lld",dp[V]);return 0;
}

但是，为了装X精益求精，我们可以继续优化。首先我们明确一下多重背包的原始转移方程：

\(dp_{i,j}=\max\limits_{k=0}^{k*v_i<=j且k<=s_i}dp_{i-1,j-k*v_i}+k*w_i\)

首先我们发现，\(dp_{i,j}\)一定是从上一层的、有关\(v_i\)与\(j\)同余的某个容量\(x\)转移来的。我们不妨记这个余数为\(r\)，然后我们把截至j的所有余数为r的容量第i层的状态都写下来，如下：

(方便起见，我们省略w、v、s数组的下标i）

\[\begin{cases} dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-v}+w,dp_{i-1,j-2*v}+2*w,\cdots,dp_{i-1,j-s*v}+s*w) \\ \\ dp_{i,j-v}=max(dp_{i-1,j-v},dp_{i-1,j-2*v}+w,dp_{i-1,j-3*v}+2*w,\cdots,dp_{i-1,j-(s+1)*v}+s*w) \\ \\ dp_{i,j-2*v}=max(dp_{i-1,j-2*v},dp_{i-1,j-3*v}+w,dp_{i-1,j-4*v}+2*w,\cdots,dp_{i-1,j-(s+2)*v}+s*w) \\ \\ \cdots \\ \\ dp_{i,r+s*v}=max(dp_{i-1,r+s*v},dp_{i-1,r+(s-1)*v}+w,dp_{i-1,r+(s-2)*v}+2*w,\cdots,dp_{i-1,r}+s*w) \\ \\ dp_{i,r+(s-1)*v}=max(dp_{i-1,r+(s-1)*v},dp_{i-1,r+(s-2)*v}+w,dp_{i-1,r+(s-3)*v}+2*w,\cdots,dp_{i-1,r}+(s-1)*w) \\ \\ \cdots \\ dp_{i,r+2*v}=max(dp_{i-1,r+2*v},dp_{i-1,r+v}+w,dp_{i-1,r}+2*w) \\ \\ dp_{i,r+v}=max(dp_{i-1,r+v},dp_{i-1,r}+w) \\ \\ dp_{i,r}=dp_{i-1,r} \\ \\ \end{cases} \]

我们从下往上去看这一坨式子，首先对于当前每一个\(j\)，它都是由之前某个容量的dp值加上装若干个\(i\)带来的价值转移来的。

假设当前容量为\(j\)，那我们令\(f_{i,k}=dp_{i,k}+(j-k)/v_i*w_i\)，保证\(k \equiv j(mod v_i)\)。显然\(dp_{i,j}\)的值就是，\([1,j]\)区间内 （注意是闭区间，也就是可以算上\(j\)） 与\(j\)同余的数中，某个这样的数对应的最大\(f_{i,k}\)。当\(j\)加上一个\(v_i\)时，显然\(j\)前的所有数的f值会加\(v_i\)，也就是相对大小关系不变。

那我们发现对于特定的\(i\)和余数\(r\)，从小到大枚举\(j\)的时候，dp_{i,j}其实就是在一个区间里找最大值而已，而且这个区间的左右端点还是单调不降的（具体请看借用过来的这个图），那我们就可以使用单调队列优化的dp求解。（不会单调队列的出门左转去找P1886，其实这个题的转移区间很类似滑动窗口)

屏幕截图 2025-08-25 123426

总之这是单调队列优化dp的一个变型，把原模板题里连续几个位置的数变成了模\(v_i\)意义下余数为\(r\)的数里，连续的几个数。时间复杂度成功被优化到\(O(nm)\)。

空间优化前是\(O(nm)\)的，实测过不去。因为第\(i\)层的结果还是只和第\(i-1\)层有关，所以可以滚动数组滚掉一维，或者新开一个拷贝数组存第\(i-1\)层的结果。总之这样下来空间复杂度就变成了\(O(m)\)。

代码（这里只放滚动数组版的）：

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
using namespace std;inline int read(){int x=0;char s=getchar();while(s<48) s=getchar();while(s>47) x=(x<<1)+(x<<3)+(s^48),s=getchar();return x;
}const int N=1010;
const int WT=2e4+2;//开大一丢丢，不然容易被卡 
int n,V,v[N],w[N],s[N],dp[2][WT],q[WT],fr,tl; signed main(){n=read(),V=read();//以下代码没有真正定义f数组，不过我们可以这么理解 for(int i=1;i<=n;i++){v[i]=read(),w[i]=read(),s[i]=read();}for(int i=1;i<=n;i++){for(int r=0;r<v[i];r++){//枚举余数 fr=1;tl=0;//每次都是赋值操作，对队头队尾指针初始化即可 for(int j=r;j<=V;j+=v[i]){while(fr<=tl&&j-q[fr]>s[i]*v[i]) fr++;//如果队头超出了区间范围就出队 while(fr<=tl&&dp[(i-1)&1][q[tl]]+(j-q[tl])/v[i]*w[i]<=dp[(i-1)&1][j]) tl--;//保证单调队列的f值单调递减，如果j前面的数的f比j小，那么j入队后队列不单调，而j迟早要入队，所以前面的元素出队 q[++tl]=j;dp[i&1][j]=dp[(i-1)&1][q[fr]]+(j-q[fr])/v[i]*w[i];//入队&统计答案 }}}printf("%lld",dp[n&1][V]);return 0;
}

四.混合背包

例题：AcWingT7

01背包、完全背包、多重背包大杂烩。

其实不难：对于第\(i\)个物品，如果它的\(s\)是-1，就走01背包转移方程；它的\(s\)是0，就走完全背包转移方程；否则走多种背包转移方程。

这里我们采用滚动数组优化空间、单调队列优化多重背包，时间复杂度\(O(nm)\)，空间复杂度\(O(m)\)。

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
using namespace std;inline int read(){int x=0;char s=getchar();while(s<48) s=getchar();while(s>47) x=(x<<1)+(x<<3)+(s^48),s=getchar();return x;
}const int N=1314;
const int WT=1314;
int n,V,v[N],w[N],s[N],dp[2][WT],q[WT],fr,tl; signed main(){n=read(),V=read();for(int i=1;i<=n;i++){v[i]=read(),w[i]=read(),s[i]=read();}for(int i=1;i<=n;i++){if(s[i]==-1){for(int j=0;j<=V;j++){dp[i&1][j]=dp[(i-1)&1][j];if(j>=v[i]){dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-v[i]]+w[i]);}}}else if(s[i]==0){for(int j=0;j<=V;j++){dp[i&1][j]=dp[(i-1)&1][j];if(j>=v[i]){dp[i&1][j]=max(dp[i&1][j],dp[i&1][j-v[i]]+w[i]);}}}else{for(int r=0;r<v[i];r++){fr=1;tl=0;//每次都是赋值操作，对队头队尾指针初始化即可 for(int j=r;j<=V;j+=v[i]){while(fr<=tl&&j-q[fr]>s[i]*v[i]) fr++;while(fr<=tl&&dp[(i-1)&1][q[tl]]+(j-q[tl])/v[i]*w[i]<=dp[(i-1)&1][j]) tl--;q[++tl]=j;dp[i&1][j]=dp[(i-1)&1][q[fr]]+(j-q[fr])/v[i]*w[i];}}	}}printf("%lld",dp[n&1][V]);return 0;
}

参考资料：
1.AcWingT3题解
2.AcWingT4题解
3.AcWingT5题解
4.AcWingT6题解
5.AcWingT11题解1
6.AcWingT11题解2
7.AcWingT12题解

相关新闻

左偏树

左偏树

左偏树以一种可以支持快速合并的数据结构。 我们对于左偏树中的每一个节点 \(u\)，我们定义 \(d_u\) 表示以 \(u\) 为根的右链的长度。假设 \(u\) 的右儿子为 \(rs\)，则 \(d_u = d_{rs} + 1\)。那么左偏树的一个性质就是对于所有节点 \(u\)，假设其左右儿子分别为 \(ls,rs\)，…

2026/7/25 11:51:07
Day4数据类型的扩展

Day4数据类型的扩展

public class Demo2 { public static void main(String[] args) {//整数拓展 二进制 八进制 十进制 十六进制0xint i= 10;int i2 = 010;//八进制0int i3 = 0x10;//十六进制0xSystem.out.println(i);System.out.println(i2);System.out.println(i3);System.out.p…

2026/7/22 1:35:21
预测2025年中科院数学候选院士上岸概率

预测2025年中科院数学候选院士上岸概率

微信视频号：sph0RgSyDYV47z6快手号：4874645212抖音号：dy0so323fq2w小红书号：95619019828B站1：UID:3546863642871878B站2：UID: 35469554100490872025 年中国科学院院士增选有效候选人名单公布，其中数学物理学部共有98 人，包含数学、物理学以及信息科学与技术的数理基础等…

2026/7/24 14:52:33

最新新闻

深入解析bq51221无线充电接收芯片：双模协议、EPT机制与通信电流限制

深入解析bq51221无线充电接收芯片：双模协议、EPT机制与通信电流限制

1. 项目概述与核心价值 在智能手机、TWS耳机乃至电动牙刷这些我们每天都要接触的设备里&#xff0c;无线充电已经从一个“酷炫”的功能变成了基础体验。但作为开发者或硬件工程师&#xff0c;当我们真正着手设计一个无线充电接收端&#xff08;RX&#xff09;时&#xff0c;会发…

2026/7/25 11:51:19
爱查宝免费 AIGC 检测效果实测与能力解析

爱查宝免费 AIGC 检测效果实测与能力解析

在内容创作日益普及的今天&#xff0c;区分“人写”还是"AI 生成”成了许多编辑、教师和内容审核者的日常难题。有时候&#xff0c;一段文字读起来流畅自然&#xff0c;却总觉得少了点“人味儿”&#xff1b;有时候&#xff0c;明明是自己亲手敲下的代码注释或文章段落&am…

2026/7/25 11:51:19
观测大模型API调用成本与延迟Taotoken用量看板使用体验分享

观测大模型API调用成本与延迟Taotoken用量看板使用体验分享

观测大模型API调用成本与延迟&#xff1a;Taotoken用量看板使用体验分享 对于依赖大模型API进行开发的团队和个人而言&#xff0c;成本控制和性能监控是项目能否持续、稳定运行的关键。直接对接多个厂商的API&#xff0c;不仅需要管理繁杂的密钥&#xff0c;更面临一个核心挑战…

2026/7/25 11:51:19
Apate文件格式伪装工具：轻松绕过文件传输限制的终极指南

Apate文件格式伪装工具：轻松绕过文件传输限制的终极指南

Apate文件格式伪装工具&#xff1a;轻松绕过文件传输限制的终极指南 【免费下载链接】apate 简洁、快速地对文件进行格式伪装 项目地址: https://gitcode.com/gh_mirrors/apa/apate 你是否曾经遇到过重要文件因格式限制无法上传到企业系统&#xff1f;或是担心隐私文件在…

2026/7/25 11:51:19
AI叙事经济学：如何用机器学习提升用户转化率

AI叙事经济学：如何用机器学习提升用户转化率

1. 叙事经济学与AI议程设置的融合价值 去年参与某金融科技项目时&#xff0c;我曾遇到一个有趣现象&#xff1a;当我们在用户调研中描述"智能投顾能像私人银行家一样24小时守护您的资产"时&#xff0c;转化率比单纯罗列算法准确率的数据高出47%。这正是叙事经济学在现…

2026/7/25 11:51:19
如何快速掌握开源工具：深蓝词库转换完整实战指南

如何快速掌握开源工具：深蓝词库转换完整实战指南

如何快速掌握开源工具&#xff1a;深蓝词库转换完整实战指南 【免费下载链接】imewlconverter ”深蓝词库转换“ 一款开源免费的输入法词库转换程序 项目地址: https://gitcode.com/gh_mirrors/im/imewlconverter 想要在不同输入法之间自由转换词库吗&#xff1f;深蓝词…

2026/7/25 11:50:36

日新闻

突破文档下载限制：kill-doc让你看到的都能保存

突破文档下载限制：kill-doc让你看到的都能保存

突破文档下载限制&#xff1a;kill-doc让你看到的都能保存 【免费下载链接】kill-doc 看到经常有小伙伴们需要下载一些免费文档&#xff0c;但是相关网站浏览体验不好各种广告&#xff0c;各种登录验证&#xff0c;需要很多步骤才能下载文档&#xff0c;该脚本就是为了解决您的…

2026/7/25 0:00:44
C++ string类模拟实现：从深拷贝到内存管理的完整指南

C++ string类模拟实现：从深拷贝到内存管理的完整指南

1. 项目概述&#xff1a;为什么我们要“手撕”string类&#xff1f;在C的学习道路上&#xff0c;尤其是从C语言过渡到C的“初阶”阶段&#xff0c;string类绝对是一个绕不开的核心。标准库里的std::string用起来太方便了&#xff0c;、find、substr&#xff0c;几个操作符和函数…

2026/7/25 0:00:44
三角洲寻宝鼠工具：高效文件搜索与资源管理实战指南

三角洲寻宝鼠工具：高效文件搜索与资源管理实战指南

1. 先搞清楚“三角洲寻宝鼠”到底是什么工具从名称来看&#xff0c;“三角洲寻宝鼠”更像是一个资源查找或文件检索类工具&#xff0c;而不是游戏或娱乐软件。这类工具的核心价值在于帮助用户快速定位特定资源&#xff0c;比如文档、图片、压缩包或特定格式的文件。如果你经常需…

2026/7/25 0:00:44

周新闻

2026年7月最新太原百达翡丽官方售后客服电话及服务网点地址查询 - 百达翡丽官方售后中心

2026年7月最新太原百达翡丽官方售后客服电话及服务网点地址查询 - 百达翡丽官方售后中心

2026年7月，百达翡丽在太原的官方售后服务体系完成更新，客户可通过全国统一客服热线与服务网点获得直接、合规的腕表养护与维修支持。所有售后服务均遵循品牌直营标准，覆盖全国范围，客户可选择到店或邮寄方式，但需…

2026/7/24 8:56:02
【JVM调优实战】16-可视化利器-JConsole-VisualVM-JMC

【JVM调优实战】16-可视化利器-JConsole-VisualVM-JMC

可视化利器：JConsole、VisualVM、JMC 实战 本文是《JVM调优实战》专栏第 16 讲。 引言 上一讲我们介绍了 JDK 命令行工具箱，它们轻量、快速，但有一个明显的短板：不直观。面对 jstat -gcutil 输出的一行行数字，你能感知 GC 频率，却难以一眼看出内存泄漏的趋势；你能用 js…

2026/7/24 8:55:54
什么是PCTFE？医药高端包装的“防潮王牌“材料

什么是PCTFE？医药高端包装的“防潮王牌“材料

——日氟荣高分子材料&#xff08;上海&#xff09;有限公司 专业深耕氟材料领域很多人好奇&#xff0c;高端药品包装为什么比普通包装更防潮、更稳定、保质期更长&#xff1f;核心秘密&#xff0c;就藏在一种特种氟材料——PCTFE聚三氟氯乙烯里&#xff01;作为国内领先的氟材…

2026/7/24 8:56:13

月新闻

[C++]内存管理：串顺序存储的内存回收

[C++]内存管理：串顺序存储的内存回收

在串&#xff08;字符串&#xff09;的顺序存储中&#xff0c;内存回收的方式取决于字符串的存储方式以及所使用的编程语言和相关库。以下以 C 为例进行说明&#xff0c;因为 C 对内存管理有较为直接的控制。 1. 基于 char 数组的串顺序存储 如果使用普通的 char 数组来存储字…

2026/7/25 11:19:17
移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试：先控制变量，再比较优化是否真的省电 摘要：功耗测试最容易犯的错误，是拿两次不同温度、不同亮度、不同场景的平均功率直接比较。本文给出一套可复现的游戏功耗测试方法，覆盖引擎特性验证、版本回归和黑盒体验测试，并说明如何把功耗与帧率、温控、CPU/G…

2026/7/25 10:36:40
足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

本文是“足球口袋教练 HarmonyOS 离线应用实战”系列第 3 篇。示例项目是一个 HarmonyOS / ArkTS / ArkUI 编写的离线足球训练助手&#xff0c;围绕真实页面、真实截图和可复现操作展开。 本篇要解决的问题 训练 App 的首页不能只展示欢迎语&#xff0c;它要解决“我现在该点哪…

2026/7/25 10:09:38