下面介绍一下背包DP主要题型
基础模型（没什么好说的，上模板）
1.01背包
最主要的模板，应用很多，很重要！！！
倒着遍历容积，不会受后选小的f[i][j]影响，已经选过的物品不会再选一遍。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=10020;
int f[N];
int n,m;
int v[N],w[N],s[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
}
2.完全背包
对于01背包来说，物品可以无限选了。
实现也很简单，只要把01背包的容积倒着遍历改为正着遍历即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=250;
int f[N];
int n,m;
int v[N],w[N];
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<"max="<<f[m];
}
3.多重背包
相较于完全背包，物品的个数有限制了。
这是加上二进制优化的最终版本，最后也是将其转化为了01背包。
点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=8000;
int n,cnt,v[N],f[N],m,C,w[N],s[N];
int main()
{
// cin>>C;
// while(C--)
// {
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int wi,vi,si;
cin>>vi>>wi>>si;
if(si>m/vi)
{
si=m/vi;
}
for(int j=1;j<=si;j<<=1)
{
v[++cnt]=j*vi;
w[cnt]=j*wi;
si-=j;
}
if(si>0)
{
v[++cnt]=si*vi;
w[cnt]=si*wi;
}
}
for(int i=1;i<=cnt;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
// }
}
4.二维背包
在容积限制的基础上又加上了质量限制，只需再加一维即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int f[N][N];
int n,M,cnt,V;
int v[N],w[N],m[N];
int main()
{
cin>>V>>M;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>m[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];j--)
{
for(int k=M;k>=m[i];k--)
{
f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
}
}
}
cout<<f[V][M];
}
5.分组背包
把物品分组，每组只能买一个。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int f[N];
int n,m,cnt;
int v[N][N],w[N][N],s[N];
int main()
{
int T,wi,ci,Ti;
cin>>m>>n>>T;
for(int i=1;i<=n;i++)
{
cin>>wi>>ci>>Ti;
s[Ti]++;
w[Ti][s[Ti]]=ci;
v[Ti][s[Ti]]=wi;
}
for(int i=1;i<=T;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=s[i];k++)
{
if(j>=v[i][k])
{
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
}
cout<<f[m];
}
这些就是基础模板，接下来是例题，你会神奇地发现原来背包还能这么用。
砝码称重
这里我们就可以抽象地把背包看成可称的重量，砝码的重量既是价值，也是容积。
最后遍历一遍有数的背包，就表示可以称出该重量。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=10020;
int f[N],w[10]={0,1,2,3,5,10,20};
int v[N],flag[N],cnt,n,m;
int main()
{
for(int i=1;i<=6;i++)
{
int x;
cin>>x;
for(int j=1;j<=x;j++)
{
n++;
v[n]=w[i];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1000;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+v[i]);
flag[f[j]]=1;
}
}
for(int i=1;i<=1000;i++)
{
if(flag[i]==1)
{
cnt++;
}
}
cout<<"Total="<<cnt;
}
新年趣事之打牌
这里主要是看一下背包找构成数的方法。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=10020;
int f[N],w[N],vis;
int v[N],flag[N],s[N],cnt,n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
w[i]=v[i];
}
f[0]=1;
for(int i=n;i>=1;i--)
{
for(int j=m;j>=v[i];j--)
{
if(f[j-v[i]]==1)
{
if(j==m)
vis++;
if(f[j]==0)
{
f[j]=1;
s[j]=v[i];//追踪
}
}
}
}
if(vis>1)
{
cout<<-1;
return 0;
}
if(f[m]==0)
{
cout<<0;
return 0;
}
int t=m;
while(t)//标记
{
flag[s[t]]=1;
t-=s[t];
}
for(int i=1;i<=n;i++)
{
if(flag[v[i]]==0)//遍历
{
cout<<i<<" ";
}
}
}
背包拓展
1.有依赖的背包
相比于普通的01背包，这里的背包有了从属关系，买有些物品的前提是先买别的。
看一道例题
这是代码的主体部分
点击查看代码
cin>>sum;//买背包所需的价值
cin>>num;//可买物品的数量
for(int j=1;j<=num;j++)
{
cin>>v[j];
cin>>w[j];
}
for(int j=0;j<sum;j++)
{
f[i][j]=-inf;//求最大，赋极小
}
for(int j=sum;j<=m;j++)
{
f[i][j]=f[i-1][j-sum];
//把上一个背包的值转移过来
}
for(int j=1;j<=num;j++)
{
for(int k=m;k>=w[j];k--)
{
f[i][k]=max(f[i][k],f[i][k-v[j]]+w[j]);
}
}//正常求在该背包下的01背包
for(int j=0;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j]);
}//比较取最大值
2.树上背包问题
有依赖的背包进阶版，详情可见我的树型DP。
3.求第k优的解
点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=2500;
int n,m,k;
int f[N][N],v[N],w[N],a[N],b[N];
int cnt,num;
//f[i][j]表示在i的容积下的第j优解
int main()
{
int T;
cin>>T;
while(T--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(f,0,sizeof(f));
memset(w,0,sizeof(w));
cnt=0;
num=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
int i,j,l;
for(i=1;i<=n;i++)
{
for(j=m;j>=v[i];j--)
{
for(l=1;l<=k;l++)
{
a[l]=f[j-v[i]][l]+w[i];
b[l]=f[j][l];
}
a[l]=b[l]=-1;//防止越界
int x,y,z;
x=y=z=1;
while(z<=k&&(a[x]!=-1||b[y]!=-1))
{
if(a[x]>b[y])
{
f[j][z]=a[x];
x++;
}
else
{
f[j][z]=b[y];
y++;
}
//排序取值
if(f[j][z]!=f[j][z-1])
//如果结果相同，舍去
{
z++;
}
}
}
}
cout<<f[m][k]<<endl;
}
}
总结
背包就总结到这里了，拜拜。