题目省略
算法1 01背包
枚举依赖的状态值,时间复杂度 $O(nv)$
由于每个主件最多依赖2个附件。则可以枚举所有可能得情况,之后转化为01背包求解。
1. 只有一个主件
2. 一个主件+附件1
3. 一个主件+附件2
4. 一个主件+附件1+附件2
这种做法的时间复杂度强依赖于附件数量,随着附件数量的增多,时间复杂度呈指数级别上升。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 +7;
const int N = 60+10;
int dp[N][32000+10],v[N],p[N],g[N];
int vv[N*4],ww[N*4];
vector<int> e[N];
int main(){
int n,m;
cin>>n>>m;
int idx=0;
for(int i = 1;i<=m;i++){
int q;
cin>>v[i]>>p[i]>>q;
if(q==0)g[++idx]=i;
else e[q].push_back(i);
}
int cnt = 0;
for(int i=1;i<=idx;i++){
cnt = 0;
int u = g[i];
vv[++cnt]=v[u];
ww[cnt]=p[u] * v[u];
int sumv =v[u],sumw=p[u] * v[u];
for(int j =0;j<e[u].size();j++){
int uu = e[u][j];
sumv+=v[uu];
sumw += p[uu] * v[uu];
vv[++cnt]=v[uu]+v[u];
ww[cnt] = p[uu] * v[uu] +p[u] * v[u];
}
if(e[u].size() >1){
vv[++cnt] = sumv;
ww[cnt] = sumw;
}
for(int j = n;j>=0;j--){
dp[i][j] = dp[i-1][j];
for(int k = 1; k<= cnt;k++){
if(j>=vv[k])
dp[i][j] = max(dp[i][j],dp[i-1][j-vv[k]]+ww[k]);
}
}
}
cout<<dp[idx][n]<<endl;
return 0;
}
算法2 01背包组合
嵌套01背包组合 $O(nv)$
在上一个方法中,我们把附件和主件的所有组合枚举。如果我们可以消除主件的影响,那么题目就会变得比较简单了,此时就是分组背包了。那么如何消除呢:
首先如果要选择附件,则必须先选择主件。因此我们可以先把主件需要的体积容量预留出来,直接选择附件。此时把附件和前面已经计算好的做01背包计算,之后再更新加上主件后的结果即。
在次过程中用到了两次01背包:
1. 第一次。处理附件:
把当前附件当做没有依赖的背包,直接按照01背包和前面已经处理好的结果做01背包
2.处理每一组依赖的时候:
上面处理好附件之后,如果这把主件加上,则这一组所能产生的价值就已经枚举完成了。此时再和前一组做01背包即可
具体见代码:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 +7;
const int N = 60+10;
int dp[32000+10],v[N],p[N], g[N],f[32000+10];
vector<int> e[N];
int main(){
int n,m;
cin>>n>>m;
int idx=0;
for(int i = 1;i<=m;i++){
int q;
cin>>v[i]>>p[i]>>q;
if(q==0)g[++idx]=i;
else e[q].push_back(i);
}
for(int i = 1;i<=idx;i++){
int u = g[i];
memcpy(f,dp,sizeof dp); // 复制上一次的结果,在上一次的结果上做01背包
for(int y = 0; y < e[u].size();y++){ //枚举附件
for(int j = n-v[u]; j>=v[e[u][y]];j--){ //预留主键的体积
f[j] = max(f[j],f[j-v[e[u][y]]]+p[e[u][y]] * v[e[u][y]]);
}
}
// 把加上主件的体积后的结果看作是一个整体,和上一次的结果做01背包
// 小于主件体积的结果则不会变,因为主件是必须要选才可以选择附件,
for (int j = n; j >= v[u]; --j)dp[j]=max(dp[j],f[j-v[u]] + v[u]*p[u]);
}
cout<<dp[n]<<endl;
return 0;
}