步骤 :
一丶状态表示
1.集合 : 题目所求问题的所有方案的集合
2.属性 : 最大值/最小值/数量
二丶状态计算
1.根据最后一步的不同,把集合划分为多个子集
分别求子集的属性,再对子集进行比较
可以分为三类题
1.01背包(2)
2.摘花生(1015)
3.最长上升子序列(895)
1. 背包问题
1.1 01背包问题
目的 : 找到一种选择方案，在背包能装下的情况下，使得选择物品的总
价值最大(每件物品最多只能用一次)
01背包根据是否选择第i件物品,也就是第i件物品选0个还是1个
把g[i][j]划分成了AB两部分
步骤 :
1.状态表示 : 用一个集合描述问题
用g[i][j]表示从前i种物品中进行选择,且总体积小于等于j
的各个选法获得的价值的集合
用f[i][j]表示从前i种物品中进行选择,且总体积小于等于j
所能获得的最大价值
即g[i][j]的最大值就是f[i][j]
2.状态计算 : 用公式推到出假设的集合
为了求出f[i][j],我们可以将g[i][j]这个集合划分成互斥的A,B两部分
A部分是选法中不包含第i件物品,B部分是选法中包含第i件物品
只要将A部分的最大值和B部分的最大值求出来
两者中较大的值就是g[i][j]的最大值,也就是f[i][j]
A部分等价于从前i-1件物品中进行选择,选出物品的总体积小于等于j
的方案获得的价值集合,也就是g[i-1][j]
g[i-1][j]这个集合中的最大值是f[i-1][j]
所以A部分的最大值就是f[i-1][j]
B部分等价于从前i件物品中选择,并且必须选择第i件物品
且选出的物品总体积小于等于j的所有方案获得的价值集合
因为B部分对应的方案中一定要选择第i件物品,这时候有两种情况
1>
给定的空间能放下第i件物品,那么第i件物品会占据𝑣𝑖的背包空间
剩下的背包空间为j-𝑣𝑖
所以B部分等价于从前i-1种物品中进行选择,选出物品的总体积小于等
j-𝑣𝑖的方案获
得的价值集合加上第i个物品的价值,也就是g[i-1][j-𝑣𝑖]+𝑤𝑖
所以B部分的最大值就是f[i-1][j-𝑣𝑖]+𝑤𝑖
2>
给定的容量不能能放下第i件物品,这时候背包里就不能放入第i件物品
因此B部分就是空集,B部分的最大值为0
3.确定初始值
01背包问题的有些状态是能够直接确定的,如f[0][m]一定等于0
有了初始值,通过i从1遍历N,j从1遍历V就能一步步求出所有的f[i][j]了
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N]; //v : 保存体积,w : 保存价值
int f[N][N]; //保存集合的最大值
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=0;i<=m;i++) f[0][i]=0; //初始化
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if(v[i]<=j) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
//能放入第i件物品的情况下,求f[i][j]
else f[i][j]=f[i-1][j];
//不能放入第i件物品的情况下,求f[i][j]
}
}
cout<<f[n][m]<<endl;
//遍历所有集合之后,就是最大值
return 0;
}
优化 :
将状态f[i][j]优化到一维f[j],即我们只讨论在i-1这一行上j的变化
f[j]表示 : 拿了总体积不超过j的物品的最大总价值
1>
为什么一维情况下枚举背包空间需要逆序？
在二维情况下,状态f[i][j]是由上一轮i-1的状态得来的
f[i][j]与f[i-1][j]是独立的,而一维状态下,只有i-1这一行
如果正序,这次枚举的i-1会把上次枚举的i-1覆盖掉
举个例子 : 假设𝑣𝑖=3
f[i][7]=max(f[i-1][7],f[i-1][4]+3)
f[i][4]=max(f[i-1][4],f[i-1][1]+3)
即 : f[7]=max(f[7],f[4]+3)
f[4]=max(f[4],f[1]+3)
如果正序,原本的f[i-1][4]+3就会被f[i][4]+3覆盖掉
2>
为什么不用讨论j<=𝑣𝑖这种情况
因为没变化
举个例子 : 原本是前4个物品放到5个空间,现在是前5个物品放到5个
空间,但是第5个放不下,所以还是前4个物品放到5个空间
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N]; //这里已经默认了f[0]=0
int main()
{
int n,m;
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]<<endl;
return 0;
}
1.2 完全背包
目的 : 找到一种选择方案，在背包能装下的情况下
使得选择物品的总价值最大(每件物品可以用无限次)
完全背包问题也是根据第i件物品的选择数量
把g[i][j]划分成不同的部分
步骤 :
1.状态表示 : 和01背包一样
2.状态计算 :
为了求出f[i][j],我们可以将g[i][j]这个集合划分成若干部分
A 部分 : 第i种物品选0件
B 部分 : 第i件物品选1件
......
X 部分 : 第i件物品选x件
A部分是第i种物品选0个对应所有选法获的价值的集合,最大值是f[i-1][j]
B部分是第i种物品选1个对应所有选法获的价值的集合,最大值是f[i-1][j-𝑣𝑖]+𝑤𝑖
X部分是第i种物品选x个对应所有选法获的价值的集合,最大值是f[i-1][j-x*𝑣𝑖]+x*𝑤𝑖
(0<=x<=j/𝑣𝑖)
3.确定初始值
完全背包问题的有些状态是能够直接确定的,如f[0][m]一定等于0
有了初始值,通过i从1遍历N,j从1遍历V就能一步步求出所有的f[i][j]了
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][N];
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=0;i<=m;i++) f[0][i]=0;
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
/*
为什么是max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])
而不是max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i])
因为k=0时,已经包含了i-1这种情况
*/
cout<<f[n][m]<<endl;
return 0;
}
优化 :
f[i][j]=max(f[i-1][j],f[i-1][j-𝑣𝑖]+𝑤𝑖,f[i-1][j-2*𝑣𝑖]+2*𝑤𝑖,f[i-1][j-3*𝑣𝑖]+3*𝑤𝑖,.....)
f[i][j-𝑣𝑖]=max(f[i-1][j-𝑣𝑖],f[i-1][j-2*𝑣𝑖]+𝑤𝑖,f[i-1][j-3*𝑣𝑖]+2*𝑤𝑖,.....)
由上两式,可得出如下递推关系 :
f[i][j]=max(f[i-1][j],f[i][j-𝑣𝑖]+𝑤𝑖)
与01背包对比 :
f[i][j]=max(f[i-1][j],f[i-1][j-𝑣𝑖]+𝑤𝑖)
可以发现我们只需把01背包问题的代码中的j改为从小到大遍历即可
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N];
int main()
{
int n,m;
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=v[i];j<=m;j++) f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}
1.3 多重背包
目的 : 找到一种选择方案,在背包能装下的情况下
使得选择物品的总价值最大(每件物品可以用的次数不一样)
和完全背包的唯一区别是这里的第i件物品不是无限个,而是s个
步骤 : 和完全背包类似
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],s[N];
int f[N][N];
int main()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=0;i<=m;i++) f[0][i]=0;
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k<=s[i]&&k*v[i]<=j;k++)
//一直装,直到第i个物品全部装完或者背包装不下
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout<<f[n][m]<<endl;
return 0;
}
优化 :
1>
可以把多重背包看成是特殊的01背包
我们可以把数量不止一个的物品拆成n个相同的物品
将其看成是n个物品,只不过他们的体积和价值都一样
2>
二进制优化
假设第i个物品有1001个,传统就是要拿1001次
二进制的思维,就是拿7个箱子就行(分别是装有512、256、128、64、32、8、1个物品的
这7个箱子),这样一来,1001次操作就变成7次操作就行了
#include<iostream>
#include<algorithm>
using namespace std;
const int N=12010,M=2010; //此处1000*log2000,向上取整数N得12000
int v[N],w[N];
int f[M];
int main()
{
int n,m;
cin>>n>>m;
int cnt=0; //箱子的个数
for (int i=1;i<=n;i++)
{
int a,b,s; //a : 体积,b : 价值,s : 数量
cin>>a>>b>>s;
int k=1; //当前箱子里应该装的物品的个数
while (k<=s)
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if (s>0) //最后一部分装不满一个箱子
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt; //用箱子的数量取代物品原本的数量
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]);
/*
比如用第1-5个箱子表示第1个物品,用第6-8个箱子表示第二个物品
这里每个箱子只能选择1次,类似01背包问题
*/
cout<<f[m]<<endl;
return 0;
}
1.4 分组背包
目的 : 找到一种选择方案,在背包能装下的情况下
使得选择物品的总价值最大(把物品分成若干组,每组有若干个物品
同一组内的物品最多只能选一个)
步骤 :
1.状态表示 :
用f[i][j]表示从前i组物品中进行选择,且总体积小于等于j
所能获得的最大价值
2.状态计算 :
为了求出f[i][j],我们可以将g[i][j]这个集合划分成若干部分
A 部分 : 不选第i组的物品
B 部分 : 选第i组的第1件物品
......
X 部分 : 选第i组的第s[i]件物品
A部分对应f[i-1][j]
B部分对应f[i-1][j-𝑣𝑖[1]]+𝑤𝑖[1]
X部分对应f[i-1][j-𝑣𝑖[s[i]]+𝑤𝑖[s[i]]
3.确定初始值 : 和01背包一样
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N];
int v[N][N],w[N][N],s[N]; //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=0;j<s[i];j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j]; 不选第i组的物品
for(int k=0;k<s[i];k++)
if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
cout<<f[n][m]<<endl;
}
优化 : 和01背包类似,只不过多分了个组
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=0;j<s[i];j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=0;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]<<endl;
}
