01背包
状态表示:二维
集合:只从前 (i) 个物品里面选择总体积 (leq j) 选法的集合
属性:选法价值的最大值
状态计算分为 放 (i) 和 不放 (i) (要不要把当前物品放进背包):
- 不放 (i) 意味着在前 (i-1) 个物品里面选,且总体积不超过 (j)
- 放 (i) 的话先来看看里面应该都是些什么东西
如图所示,(f[i][j]) 表示的是 (0) 至 (i) 里面所有选法的权值和的最大值,我们可以将 (f[i][j]) 拆成两部分来看待,即 (f[i-1][j-v[i]]) 和 (i)
那么这两段的权值和为 (f[i-1][j-v[i]]+w[i]) ,由于求最大值,所以我们要比较一下那种选择可以使权值最大,于是我们就得到了状态转移方程
由于下标不能是负数,所以上述转移方程要求 (jgeq w[i]) 。当 (j<w[i]) 时,(f[i][j]=f[i-1][j])
综上所述,可以得出:
#include <iostream>
using namespace std;
const int N = 1010;
int f[N][N],v[N],w[N];
int n,m;
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=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
注意题目给的数据,我们的数组的第二维是跟着容量的范围而不是物品数的范围
优化版本:
我们可以发现在 (f[i][j]) 的时候只用到了 (f[i-1][j]) ,这样 (f[i-2][j]),(f[i-3][j]) …… 就被浪费掉了,而且,我们二维的状态只用到了(j) 和 (j-w_i) 都是 (leq j) 不会在两侧,于是我们就可以用滚动数组来优化这个问题
首先,我们直接删除掉 (i) 这个状态,那么原方程就会变成:
由于 (f[j]=f[j]) 是恒等式,直接删去,由于 (max(f[j],f[j-v[i]]+w[i])) 要求 (jgeq w[i]) ,所以 (j) 直接从 (w[i]) 开始枚举
好,接下来再看变形后的式子与原来的方程是否是等价的,答案是否定的
由于我们的 (j) 是从小到大枚举的,所以 (j-v[i]) 会在 (j) 之前被算,相当于二维的 (f[i][j-v[i]]) 与原来的方程不符,那么如何解决这个问题呢? 我们可以让 (j) 从大到小枚举,这样就保证了当我们计算 (f[j]) 的时候 (f[j-v[i]]) 因为比 (j) 小,所以还没有被更新,用的就是 (i-1) 层的 (f[j-v[i]]) ,问题解决
01背包如何保证拿一次? 那么当前背包的体积就要去找前面的,而前面的都肯定是没有拿过这个物品的,所以可以保证只拿一次。
当然我们可以边输入边计算,又可以省下数组的空间
#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w;
cin>>v>>w;
for(int j=m;j>=v;j--)
f[j]=max(f[j],f[j-v]+w);
}
cout<<f[m];
return 0;
}
完全背包
状态表示:二维
集合:所有只考虑前 (i) 个物品,且总体积 (leq j) 选法的集合
属性:选法价值的最大值
状态计算以第 (i) 个物品选几个为划分,注意体积不能超过 (j) ,即 (k×v[i]leq j)
注意当 (k=0) 时就相当于不选,所以需要从 (0) 开始枚举,这里还需要对 (f[i][j]) 打擂台,有别于01背包
我们可以得出状态转移方程
#include <iostream>
using namespace std;
const int N = 1010;
int f[N][N],v[N],w[N];
int n,m;
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=0;j<=m;j++)
for(int k=0;k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
cout<<f[n][m];
return 0;
}
那么这样的时间复杂度大概是 (O(m^2n)) 的,显然不行
我们来想想如何优化
首先,将原方程展开得:
然后再与 (f[i][j-v[i]]) 做一下对比:
那么我们可以发现,(f[i][j]) 仅仅比 (f[i][j-v[i]]) 多了一个 (f[i-1][j]) ,然后后面的每一项都多一个 (w[i])
于是我们就可以将 (f[i][j-v[i]]) 加上 (w[i]) 转化成 (f[i-1][j-v[i]]+w[i],f[i-1][j-2×v[i]]+2×w[i],...)
再与 (f[i-1][j]) 比较一下最大值就行了
于是我们就得到了优化后的状态转移方程
#include <iostream>
using namespace std;
const int N = 1010;
int f[N][N],v[N],w[N];
int n,m;
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=0;j<=m;j++)
{
if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
else f[i][j]=f[i-1][j];
}
cout<<f[n][m];
return 0;
}
我们可以发现,这个方程跟01背包非常像,所以我们可以按照01背包的思路优化成1维
注意完全背包跟01背包唯一的区别就在于01背包是 (f[i-1][j-v[i]]+w[i]) 而完全背包是 (f[i][j-v[i]]+w[i])
完全背包没有 -1 这个问题,所以从小到大遍历,从大到小是不行的,从大到小会使得每个物品就拿一次(参见01背包的优化)
从大到小的话会导致 (f[j]) 在 (f[j-v[i]]) 之前算,导致算 (f[j]) 的时候用的 (f[j-v[i]) 的值是 (i-1) 层的,变成01背包了
#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w;
cin>>v>>w;
for(int j=v;j<=m;j++)
f[j]=max(f[j],f[j-v]+w);
}
cout<<f[m];
return 0;
}
多重背包
状态表示:二维
集合:所有只从前 (i) 个物品中选,并且总体积 (leq j) 选法的集合
属性:每一个选法对应的总价值的最大值
状态计算和完全背包非常像,不过将 (k) 枚举结束的条件改成 (s) 个
不过这样的时间复杂度很高,(O(m^2n))
#include <iostream>
using namespace std;
const int N = 105;
int f[N][N];
int v[N],w[N],s[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=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
cout<<f[n][m];
return 0;
}
然后我们尝试优化,既然和完全背包很像,我们先来试试通过完全背包的方式优化
首先将原方程展开得:
再对比 (f[i][j-v[i]]) :
我们发现两个式子很像,不过,(f[i][j-v[i]]) 多了一项 (f[i-1][j-(s[i]+1)w[i]]+s[i]×w[i])) ,我们不可以通过前 (n) 个数的最大值和最后一个数,求出前 (n-1) 个数的最大值,所以这样的方法是不可行的
我们可以用二进制的方式来优化
例如当 (s=1023) 时,我们真的需要从 (0) 枚举到 (1023) 吗?
我们可以将若干个 (i) 个物品打包,比如说我们可以打包成10组:(1,2,4,8,...512)
每组最多选一次,我们可以用这10组凑出来 (0) 到 (1023) 的任何数(二进制可以表示出所有的十进制整数)
那么对于任何一个 (s),我们将物品打包成 (2^0,2^1,2^2,...,2^k),(2^0) 一直加到 (2^k leq s)
如果 (2^0) 一直加到 (2^k < s),再补上一个 (c)
那么显然有 (c<2^{k+1})
那么来证明一下是不是这样就能表示出 (0) 到 (s) 的所有数?
首先,(2^0) 一直加到 (2^k) 能凑出 (0) 到 (2^{k+1}-1) 的所有数(等比数列公式)
补上 (c) 以后便能凑出 (0) 到 (2^{k+1}+c) 的所有数,(2^{k+1}+c) 即 (s)
所以是可行的,我们将原本的 (O(m^2 n)) 优化到了 (O(m^2 logn))
转化完之后再求一遍01背包就行了
注意我们的打包时数组体积的部分要开 (log_2 2000×1000) (log_22000) 要上取整得 (12)
#include <iostream>
using namespace std;
const int N = 25000;
int n,m;
int v[N],w[N],f[N];
int main()
{
cin>>n>>m;
int cnt=0; //重新打包后物品的个数
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1; //2的k次幂
while(k<=s)
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
//补上的c
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]);
cout<<f[m];
return 0;
}
其实还有单调队列的优化方式,不过是提高的内容,等我之后滚回来更新
分组背包
状态表示:二维
集合:只从前 (i) 个物品里面选,且总体积 (leq j) 的所有选法
属性:选法价值的最大值
状态计算:枚举第 (i) 组,物品选第几个或不选
不选也就是 (f[i-1][j])
选第 (k) 个也就是 (f[i-1][j-v[i][k]]+w[i][k])
注意 (k) 枚举的是下标,所以从0开始
#include <iostream>
using namespace std;
const int N = 105;
int f[N][N],v[N][N],w[N][N],s[N];
int n,m;
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];
for(int k=0;k<s[i];k++)
{
if(v[i][k]<=j)
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m];
return 0;
}
直接删去一维,得到状态转移方程
#include <iostream>
using namespace std;
const int N = 105;
int f[N],s[N],v[N][N],w[N][N];
int n,m;
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(v[i][k]<=j)
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
cout<<f[m];
return 0;
}
混合背包
此为几种背包的模型(01背包、多重背包、完全背包)的综合使用,所以如果弄懂了前几种背包模型,混合背包的问题也会迎刃而解,这里主要介绍一种写法使得代码可读性变高
首先我们知道多重背包实际上是转化为01背包来做的,所以我们如果遇到多重背包时,我们直接将它加进去,最后当作01背包解决就行了
在代码中,我使用了结构体,一个是物品的种类,另外两个是体积和权值
输入多重背包的时候,直接二进制优化好再加进 vector 就行了
最后根据物品类型的不同分别处理就行了
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int f[N];
struct Thing
{
int kind,v,w;
};
vector<Thing> things;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
if(s==-1) things.push_back({0,v,w});
else if(s==0) things.push_back({1,v,w});
else
{
int k=1;
while(k<=s)
{
things.push_back({0,v*k,w*k});
s-=k;
k*=2;
}
if(s>0) things.push_back({0,v*s,w*s});
}
}
for(auto thing:things)
{
if(thing.kind==0)
{
for(int j=m;j>=thing.v;j--)
{
f[j]=max(f[j],f[j-thing.v]+thing.w);
}
}
else
{
for(int j=thing.v;j<=m;j++)
{
f[j]=max(f[j],f[j-thing.v]+thing.w);
}
}
}
cout<<f[m];
return 0;
}
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!