完全背包求方案数
注意:这里的答案是阶乘级别，需要用long long存储
代码:
#include <iostream>
using namespace std;
const int N=3010;
long long f[N];
int n,m;
int main()
{
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
for(int j=a;j<=m;j++)
f[j]+=f[j-a];
}
cout<<f[m]<<endl;
return 0;
}
朴素版的多重背包问题能过
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int M=6060;
int f[M];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
for(int j=m;j>=0;j--)
for(int k=0;k<=s&&k*v<=j;k++)
f[j]=max(f[j],f[j-k*v]+k*w);
}
cout<<f[m]<<endl;
return 0;
}
01背包问题求方案数的应用
DP:
1.状态表示：f[i][j]表示从前i个物品中选，且体积恰好为j的方案的总数
2.状态计算:
1. 当不选第i个物品时，f[i][j]=f[i-1][j];
2. 当选择第i个物品时，f[i][j]+=f[i][j-v]
初始化时，只有f[0][0]是合法方案(空集，算一种方案，就是什么都不选且也不需要选)，其余的f[0][1]~f[0][m]都不合法，为了让他不参与运算，赋值为0
代码:
#include <bits/stdc++.h>
using namespace std;
const int M=10010;;
int f[M];
int n,m;
int main()
{
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++)
{
int v;
cin>>v;
for(int j=m;j>=v;j--)
f[j]+=f[j-v];
}
cout<<f[m]<<endl;
return 0;
}
这一题主要是要掌握这三种状态的表示:
1. f[i][j]所在集合:表示从前i个物品中选，体积最多j的方案数
初始值全为0，并且要保证j-v>=0
2. f[i][j]所在集合:表示从前i个物品中选，体积恰好j的方案数
初始值只有f[0][0]为0，并且为了识别非法状态，将其赋值为一个不参与运算的数，并且要保证j-v>=0
3. f[i][j]所在集合:表示从前i个物品中选，体积至少j的方案数
初始值只有f[0][0]为0，并且为了识别非法状态，将其赋值为一个不参与运算的数,此时j-v可以为负数
DP:
1. 状态表示:f[i][j][k]表示从前i个物品中选，并且费用1总数至少为j、费用2总数至少为k的最小值
2. 状态计算:和二维的01背包一样
但是虽然这一题f[i][-x][-y]合法，但是由于数据都>=1，这些的最小值都为f[i][0][0]
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=30,M=90;
int f[N][M];
int n,m,k;
int main()
{
cin>>n>>m>>k;
memset(f,0x3f,sizeof f);//为了确保不用非法值
f[0][0]=0;
for(int i=1;i<=k;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int j=n;j>=0;j--)
for(int x=m;x>=0;x--)
f[j][x]=min(f[j][x],f[max(j-a,0)][max(x-b,0)]+c);
}
cout<<f[n][m]<<endl;
return 0;
}
二维费用的背包问题可以与所有背包问题相结合
这一题是与01背包相结合
它的状态表示、状态计算以及优化与01背包几乎一样，就是维度升了一维
代码:
#include <bits/stdc++.h>
using namespace std;
const int V=110,M=110;
int f[V][M];
int n,v,m;
int main()
{
cin>>n>>v>>m;
for(int i=1;i<=n;i++)
{
int sv,sm,w;
cin>>sv>>sm>>w;
for(int j=v;j>=sv;j--)
for(int k=m;k>=sm;k--)
f[j][k]=max(f[j][k],f[j-sv][k-sm]+w);
}
cout<<f[v][m]<<endl;
return 0;
}
对于完全背包的优化，我们发现他是求所有前缀中的最大值，所以用一个变量来更迭，只是这个变量恰好是f[i,j-v]+w
而对于多重背包的优化，我们要求的是中间一段的最大值，就算我们知道某几个确定元素和整体的最大值
由于存在不等关系，也无法知道区间内的最大值，所以无法使用完全背包问题的优化方式
但是通过对比f[i,j],f[i,j-v],f[i,j-2v],f[i,j-3v]...,f[i,j-kv]
我们可以发现j,j-v,j-2v,...,j-kv都有一个特点，就是模v的余数r相同(也就是j一直减v,最后不够减去v的体积)
这样就用r把j,j-v,j-2v,…,j-kv这些数从后面最小的j-kv转化为到了[r,r+v,r+2v,...,j-v,j]
求f[i,j]就是求[r,r+v,r+2v,…,j-v,j]中包含j-v往前的s个数的最大值，取不到s个就特判成有几个取几个,f[i,j-kv]也是以此类推
这种数据结构就对应了基础课的单调队列
所以多重背包的优化就是求长度固定为s的滑动窗口中的最大值，但因为每个f[i,j-kv]之间存在一个偏移量，所以还要加上一个关于w的偏移量
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=20010;
int f[N];
int g[N];//用滚动数组存储上一层的f[i];
int q[N];//队列
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
memcpy(g,f,sizeof f);//先把枚举前的那一层状态存下来
for(int r=0;r<v;r++)//枚举余数，最小是0(表示m%v==0),最大<v(表示kv->m,但是小于m)
{
int hh=0,tt=-1;//定义单调队列的头和尾
for(int k=r;k<=m;k+=v)//枚举坐标轴上的值，从余数r开始，到放不下结束
{
if(hh<=tt && q[hh]<k-s*v) hh++;
//下标都是v的整数倍，如果k-s*v>q[hh],说明q[hh]这个数已经在窗口外面，hh++让它出队
if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);//求的是窗口内部最大值
//q[hh]就是最大值的下表,所以g[q[hh]]就是f[]的最大值，后面还要加上窗口内元素个数*w,
while(hh<=tt&& g[q[tt]]-(q[tt]-r)/v*w <= g[k]-(k-r)/v*w) tt--;
//单调队列弹出不合法元素(要求队列递减)
q[++tt]=k;
}
}
}
cout<<f[m]<<endl;
return 0;
}
二维费用的01背包问题
费用V1:精灵球的数量
费用V2:皮卡丘的体力
价值:精灵本身
状态表示和计算与01背包问题一样
同样这一题可以把第一维优化掉
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1010,M=510,K=110;
int f[N][M];
int V1,V2,n;
int main()
{
cin>>V1>>V2>>n;
for(int i=1;i<=n;i++)
{
int v1,v2;
cin>>v1>>v2;
for(int j=V1;j>=v1;j--)
for(int k=V2-1;k>=v2;k--)
f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);
}
cout<<f[V1][V2-1]<<' ';
int t=1e9;
for(int j=0;j<=V2-1;j++)
if(f[V1][V2-1]==f[V1][j])
t=min(t,j);
cout<<V2-t<<endl;
return 0;
}
完全背包求方案数
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int w[5]={0,10,20,50,100};
int n;
int main()
{
cin>>n;
f[0]=1;//一本书都不买也是一种方案
for(int i=1;i<=4;i++)
{
for(int j=w[i];j<=n;j++)
f[j]+=f[j-w[i]];
}
cout<<f[n]<<endl;
return 0;
}
和普通的01背包没什么区别，就是w[]和v[]是同一个
代码1:朴素版
#include <iostream>
#include <algorithm>
using namespace std;
const int N=40,M=20020;
int f[N][M];
int v[N];
int n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+v[i]);
}
cout<<m-f[n][m]<<endl;
return 0;
}
代码2:优化版
#include <iostream>
#include <algorithm>
using namespace std;
const int N=40,M=20020;
int f[M];
int v[N];
int n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>v[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]]+v[i]);
cout<<m-f[m]<<endl;
return 0;
}
01背包问题加了一个背景
代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110,M=1010;
int f[M];
int w[N],t[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>t[i]>>w[i];
for(int i=1;i<=m;i++)
for(int j=n;j>=t[i];j--)
f[j]=max(f[j],f[j-t[i]]+w[i]);
cout<<f[n]<<endl;
return 0;
}
