文章目录
一.01背包
一直背包问题都是套模板，就没弄明白过，今天来理解理解~~~
① 01背包（1.0）
首先就是最原始的二维的背包，未优化的劣势就是空间复杂度太大，数据大了装不下，但原始的好处是可以回溯看具体哪个物品放了，哪个没放，因为所有信息都记录下来了嘛：
其中
if(j<c)dp[i][j]=dp[i−1][j]
这句话必须写，我之前就受空间优化的影响。。。没写这句话，，，在此感谢我滴队友 Lzj 童鞋~因为如果不写就有可能因为没转移到而变成0
#include"iostream"
#include"cstring"
using namespace std;
const int maxn=1e5+5;
int dp[110][maxn];
int pre,now;
int N,W;//N表示物品个数，W表示背包容量
int vis[110];
int C[110],V[110];
/*用来回溯，看哪些用了哪些没用*/
void traceback()
{
int w=W;
for(int i=N;i>1;i--)
{
if(dp[i][w]==dp[i-1][w])vis[i]=0;
else
{
vis[i]=1;
w-=C[i];
}
}
if(dp[1][w])vis[1]=1;
else vis[1]=0;
for(int i=1;i<=N;i++)cout<<vis[i]<<" ";
cout<<endl;
}
void print()
{
for(int i=1;i<=N;i++)
{
for(int j=1;j<=W;j++)cout<<dp[i][j]<<" ";
cout<<endl;
}
}
int main()
{
while(cin>>N>>W)
{
memset(dp,0,sizeof(dp));
pre=0;
for(int i=1;i<=N;i++)
{
int c,v;
cin>>c>>v;
C[i]=c,V[i]=v;
for(int j=1;j<=W;j++)
{
if(j<c)dp[i][j]=dp[i-1][j];/*都小于了，说明第i个装不下，直接不要*/
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-c]+v);
}
}
cout<<dp[N][W]<<endl;
print();
traceback();
}
}
② 01背包（2.0）
因为我们大多数时候要的是最后答案，而整个计算过程只与这一次和上一次有关，于是优化为滚动数组：
#include"iostream"
#include"cstring"
using namespace std;
const int maxn=1e5+5;
int dp[2][maxn];
int pre,now;
int N,W;//N表示物品个数，W表示背包容量
void bag01(int v,int c)//v表示价值，c表示重量
{
now=pre^1;
for(int j=1;j<=W;j++)
{
if(j<c)dp[now][j]=dp[pre][j];
else dp[now][j]=max(dp[pre][j],dp[pre][j-c]+v);
}
pre=now;
}
int main()
{
while(cin>>N>>W)
{
memset(dp,0,sizeof(dp));
pre=0;
for(int i=1;i<=N;i++)
{
int c,v;
cin>>c>>v;
bag01(v,c);
}
cout<<dp[now][W]<<endl;
}
}
③ 01背包（3.0）
接下来就是烧脑的时候了：
假设我们去掉第一维
我们假设算 dp[10]的时候有一个重量为3，价值为999的东西，那么写出来就是：
dp[10]=max(dp[10],dp[10−3]+999)
即：
dp[10]=max(dp[10],dp[7]+999)
而这里的 dp[7]要的是上一次的 dp[7]
相当于：
dp[i][10]=max(dp[i][10],dp[i−1][7]+999)
那么怎样保证是上一次的 dp[7]喃？
我以前就一直没懂为啥要倒着来遍历。。。
因为你正着来嘛，弄到 dp[10]的时候, dp[7]就已经更新过了，相当于已经是 dp[i][7]了
转移方程就变成了： dp[i][10]=max(dp[i][10],dp[i][7]+999)，这样就错了
而如果倒着来， dp[7]还没有更新过，就还是 dp[i−1][7]
所以要倒着来
而且~~~~
遍历的时候直接只用便利到 c[i]，因为小于 c[i]的时候是直接 dp[i][[j]=dp[i−1][j]的，相当于上一次与这一次没区别，既然没区别就懒得再去遍历了，反正都是那么多了
而且写了貌似还要遭。。。因为要数组越界。。。。
这个就阔以算是最后版本了，以后当模板用~
#include"iostream"
#include"string.h"
#include"algorithm"
using namespace std;
const int maxn=1e4+5;
int dp[maxn];
int N,W;
void bag01(int c,int v)
{
for(int i=W;i>=c;i--)
{
dp[i]=max(dp[i],dp[i-c]+v);
}
}
int main()
{
while(cin>>N>>W)
{
for(int i=0;i<N;i++)
{
int c,v;
cin>>c>>v;
bag01(c,v);
}
cout<<dp[W]<<"\n";
}
}
关于初值：
一种是不要求背包装满，这个时候 dp要初始化为0
另一种就是，要求背包装满，只有 dp[0]=0，其他 dp初始化为 −∞
唉~不懂，听别的小朋友说，初始化的意思就是说，背包要属于“合法”状态，
比如 不要求背包装满： dp[0]=0是阔以的嘛，我啥都不装是阔以滴嘛~
但是要求装满的时候 dp[100]=0是啥意思？包包都是满的，那肯定是有装东西滴，那有装东西你还价值为0？？？
这样不是就矛盾了么~就处于一个 “未定义” 状态，所以要初始化为 −∞
二.完全背包
完全背包就是第i个物品有很多个，阔以拿0个，1个，2个。。。。。
所以1.0版本就不来了，直接来2.0版本的滚动数组：
② 完全背包（2.0）
#include"iostream"
#include"cstring"
using namespace std;
const int maxn=1e5+5;
int dp[2][maxn];
int pre,now;
int N,W;//N表示物品个数，W表示背包容量
void bagall(int v,int c)//v表示价值，c表示重量
{
now=pre^1;
for(int j=1;j<=W;j++)
{
for(int k=0;k*c<=j;k++)//这件物品取0个，1个，2个。。。。
{
//如果剩下的空间还能再放一个
if(c<=j)dp[now][j]=max(dp[pre][j],dp[pre][j-k*c]+k*v);
//再多放一个都不得行
else dp[now][j]=dp[pre][j];
}
}
pre=now;
}
int main()
{
while(cin>>N>>W)
{
memset(dp,0,sizeof(dp));
pre=0;
for(int i=1;i<=N;i++)
{
int c,v;
cin>>c>>v;
bagall(v,c);
}
cout<<dp[now][W]<<endl;
}
}
然后烧脑的3.0版本来了~
因为第 i个物品有很多个，那我就考虑我当前这个情况再多放一个要不要得~
那写出来就是
dp[i][j]=max(dp[i−1][j],dp[i][j−c]+v)
要不得我就继承 dp[i−1][j]的
要得的话我就多放一个 dp[i][j−c]+v
那这个样子就好理解为啥完全背包要正着来了嘛，我要的就是更新之后的，
算 dp[10]的时候，要的就是更新后的 dp[7],so~
③ 完全背包（3.0）
#include"iostream"
#include"cstring"
using namespace std;
const int maxn=1e5+5;
int dp[2][maxn];
int pre,now;
int N,W;//N表示物品个数，W表示背包容量
void bagall(int v,int c)//v表示价值，c表示重量
{
for(int j=c;j<=W;j++)
{
dp[j]=max(dp[j],dp[j-c]+v);
}
}
int main()
{
while(cin>>N>>W)
{
memset(dp,0,sizeof(dp));
pre=0;
for(int i=1;i<=N;i++)
{
int c,v;
cin>>c>>v;
bagall(v,c);
}
cout<<dp[now][W]<<endl;
}
}
三.多重背包
01背包 和完全背包 理解了那么 多重背包 就好理解了~
因为就算用的这两个~
多重背包就是第 i 种物品有 ni 个。
##① 多重背包（1.0）
那么我们阔以把这 ni 个物品分别都 01背包 一哈，这个（1.0）版本的太暴力了，就不写了，直接来2.0版本~
##② 多重背包（2.0）
2.0版本就是我们把 ni 拆成一坨一坨的，拆成 20,21,22,23.....就像快速幂那样，这样就算 ni 很大，也只有对数级别的几个~
264个这种物品也只有 64 坨~
然后剩下不够 2 的多少次方的又看成一坨就行了
#include"iostream"
#include"string.h"
#include"algorithm"
using namespace std;
const int maxn=1e5+5;
int dp[maxn];
int N,W;
void bag01(int c,int v)
{
for(int i=W;i>=c;i--)
{
dp[i]=max(dp[i],dp[i-c]+v);
}
}
void bagall(int c,int v)
{
for(int i=c;i<=W;i++)
{
dp[i]=max(dp[i],dp[i-c]+v);
}
}
void bagmul(int c,int v,int n)
{
//如果背包装不完所有的这种物品，那相当于就算无穷多个嘛，无穷多个就装不完嘛~
if(n*c>W)
{
bagall(c,v);
return;
}
int k=1;
while(n)
{
if(n<k)break;
bag01(c*k,v*k);
n-=k;
k<<=1;
}
//剩下的又分成一坨~
bag01(c*n,v*n);
}
int main()
{
while(cin>>N>>W)
{
for(int i=0;i<N;i++)
{
int c,v,n;
cin>>c>>v>>n;
bagmul(c,v,n);
}
cout<<dp[W]<<"\n";
}
}
③ 多重背包（3.0）
用单调队列优化。。。我不会。。。。以后再说。。。。。
最后一个阔以作为模板了~
要是出现背包问题的裸题，那么就阔以把他秒了~
四.大01背包
大01背包问题就是背包容量特别大，普通的01背包无论是时间上还是空间上都会炸掉
但是像这一类题目会发现： 价值∗物品个数 很小
也正因为这样才阔以dp，只是 max变成了 min
关于初值
dp[i][j]表示前 i个物品中，价值为 j的所需要的最小的容量
不理解的地方：照理说 dp表示的是最小值，但是为什么初值还是 dp[pre][0]=0而不是弄成 ∞
② 大01背包（2.0）
还是 2.0版本的滚动数组
#include"iostream"
#include"cstring"
using namespace std;
const int maxn=1e4+5;
int dp[2][maxn];
int N,W;//W是背包容量
int CC,VV;
int now,pre;
int res;
void Bigbag01(int v,int c)
{
now=pre^1;
for(int i=0;i<=VV;i++)
{
if(i>=v)dp[now][i]=min(dp[pre][i],dp[pre][i-v]+c);
else dp[now][i]=dp[pre][i];
if(dp[now][i]<=W)res=max(res,i);//在这里找最大的结果
}
pre=now;
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(dp,0x3f,sizeof(dp));
res=-1;
pre=0;
cin>>N>>W;
int v[maxn],c[maxn];
CC=0,VV=0;
for(int i=1;i<=N;i++)
{
cin>>c[i]>>v[i];
CC+=c[i],VV+=v[i];
}
dp[pre][0]=0;
for(int i=1;i<=N;i++)
{
Bigbag01(v[i],c[i]);
}
cout<<res<<endl;
}
}
③ 大01背包（3.0）
#include"iostream"
#include"cstring"
using namespace std;
const int maxn=1e4+5;
int dp[maxn];
int N,W;//W是背包容量
int CC,VV,res;
void Bigbag01(int v,int c)
{
for(int i=VV;i>=v;i--)
{
dp[i]=min(dp[i],dp[i-v]+c);
if(dp[i]<=W)res=max(res,i);
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
res=-1;
memset(dp,0x3f,sizeof(dp));
cin>>N>>W;
int v[maxn],c[maxn];
CC=0,VV=0;
for(int i=1;i<=N;i++)
{
cin>>c[i]>>v[i];
CC+=c[i],VV+=v[i];
}
dp[0]=0;
for(int i=1;i<=N;i++)
{
Bigbag01(v[i],c[i]);
}
cout<<res<<endl;
}
}
京公网安备 11010502036488号