分组背包问题
题目 分组背包问题
思路分析
从另一个角度 多加一个维度
现在是每类物品里选一个 多了个类这一维
但是因为只能选一个 所以还是可以当做01去写
朴素做法
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
//由n种物品变成了n类物品 然后又要在每类里面去选
//所以就是多了一维
int v[N][N],w[N][N],s[N];
int f[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=0;j<=m;j++){
f[i][j]=f[i-1][j]; //不选
for(int k=0;k<s[i];k++){
//第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];
return 0;
}
因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
//由n种物品变成了n类物品 然后又要在每类里面去选
//所以就是多了一维
int v[N][N],w[N][N],s[N];
int f[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(j>=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[m];
return 0;
}
发现万变不离其宗
再往后可能就是物品分类 且其中可选多个（又分带不带物品数量限制）
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int v[N][N],w[N][N],s[N];
int f[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=0;j<=m;j++){
f[i][j]=f[i-1][j];
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];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int v[N][N],w[N][N],s[N];
int f[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(j>=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
cout<<f[m];
return 0;
}
💬 评论