以下所有问题的考虑均基于方案挑选中商品的顺序没有影响,即挑选(1,2,3)和挑选(3,2,1)是等价方案
如果不存在此种假设,则f[i][j]需要改变为:挑选方案组合长度为i,方案总和为j的方案数
初始化问题
初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态
譬如当要求恰好装满时,f[0]初始化为0,f[1,…]=-∞,因为不放入任何物品时体积只能恰好为0,而其他的体积不可能在什么都不放入的情况下合法
如果要求至多,则均可达到合法状态,因为都可以”什么都不装”,此时价值为0,所以f[0…]初始化为0
1.恰好——>
2.至多——>下面给出的背包模型都是体积至多为v,dp数组全为0即可
3.至少——> 入口为0,其余全为INF 1020. 潜水员
最大价值问题
01背包$\quad$O(nm)
423. 采药
1024. 装箱问题
1022. 宠物小精灵之收服 (二维)
f(i,j)集合的表示:前i个物品中,体积不超过j的选法
f(i,j)集合的内容:前i个物品中,体积不超过j的选法的最大价值
状态计算的思想:
-
决策:选第i个,不选第i个——>由集合的表示入手
-
决定:取最大值——>由集合的内容决定
f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i])
逆向枚举进行空间优化 如果优化成一维,一定要逆序,否则状态转移就不对了(数字组合)
f(j)=max(f(j),f(j-v[i])+w[i])
完全背包$\quad$O(nm)
f(i,j)集合的表示:前i个物品中,体积不超过j的选法
f(i,j)集合的内容:前i个物品中,体积不超过j的选法的最大价值
状态计算的思想:
-
决策:选几个第i个,不选第i个——>由集合的表示入手
-
决定:取最大值——>由集合的内容决定
f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i])
正向枚举进行空间优化
f(j)=max(f(j),f(j-v[i])+w[i])
分组背包$\quad$O(nmk)
f(i,j)集合的表示:前i组物品中,体积不超过j的选法
f(i,j)集合的内容:前i组物品中,体积不超过j的选法的最大价值
状态计算的思想:
-
决策:选第i组第k个,不选第i组——>由集合的表示入手
-
决定:取最大值——>由集合的内容决定
f(i,j)=max(f(i-1,j),f(i-1,j-v[i][k])+w[i][k])
逆向枚举进行空间优化(j循环条件不能直接跟01背包一样,因为是小于该组体积最小的,放到j循环里单独判断更新)
f(j)=max(f(j),f(j-v[i][k])+w[i][k])
多重背包$\quad$O(nmk)—>O(nmlogk)->O(nm)
01背包是多重背包的一个特例,即s=1
f(i,j)集合的表示:前i个物品中,体积不超过j的选法
f(i,j)集合的内容:前i个物品中,体积不超过j的选法的最大价值
状态计算的思想:
-
状态划分:第i个物品选k个,不选第i个物品——>由集合的表示入手
-
对状态进行的操作:取最大值——>由集合的内容决定
f(i,j)=max(f(i-1,j),f(i-1,j-v[i]*k)+w[i]*k)
逆向枚举进行空间优化(j<=k*v[i])
f(j)=max(f(j),f(j-v[i]*k)+w[i]*k)
优化方法
- 二进制枚举
由于每个数字都可以由二进制数表示,第i个物品的个数k,1~k也同样可以由一堆2的指数构成的数相加得到.
这样就把多重背包转化成了 0-1背包
将k分解成以2为公比的等比数列, 每次挑选不同的项,相当于选取不同个数的第i个物品
for(int i=1;i<=n;i++)
{
cin>>v>>w>>s;
for(int k=1;k<=s;k*=2)
{
for(int j=m;j>=k*v;j--)
{
f[j]=max(f[j],f[j-k*v]+k*w);
s-=k;
}
}
if(s)
{
for(int j=m;j>=s*v;j--)
f[j]=max(f[j],f[j-s*v]+s*w);
}
}
- 单调队列
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20010;
int n,m,v,w,s;
int f[N];
struct node{
int pos,dp;
}q[N];
int main()
{
cin>>n>>m;
while(n--)
{
cin>>v>>w>>s;
for(int j=0;j<v;j++)
{
int hh=0,tt=-1,stop=(m-j)/v;
for(int k=0;k<=stop;k++)
{
int val=f[k*v+j]-k*w;
while(hh<=tt&&val>=q[tt].dp) tt--;
q[++tt].pos=k,q[tt].dp=val; //tt指向不在序列里的位置记得要tt++
while(q[hh].pos<k-s) hh++; //应该是k-s而不是s-k
f[k*v+j]=q[hh].dp+k*w;
}
}
}
cout<<f[m];
}
混合背包
7. 混合背包问题
混合背包就是01背包,完全背包,多重背包 的混搭.有些物品属于完全背包物品的性质,有些属于分组背包的性质.
01背包是多重背包的特殊情况,所以可以变成完全背包和多重背包的结合
判断是哪种类型的背包问题然后写下对应的状态转移方程即可
有依赖背包
方案数问题
对选法不作特殊要求的方案数
集合划分:选第i个能够到达要求j(f[i][j]),不选第i个能够到达要求J(f[i-1][j-w[i]]),方案数为两者和
初始化:要求j=0,什么都不选是一种方案
