详细的分组背包说明和模板参考AcWing 9. 分组背包问题
分组背包求每个方案模板题
注意这里不能用滚动数组进行优化,因为要记录每一步的状态,为了最后求每一步的最优解,而滚动数组会覆盖掉前面的状态
转化为分组背包的条件:
如果题目给出了多组数据,表示不同组的不同选择,并且同一个的每个选择之间是互斥的,说明一个组只能选择一个选择
,那么就可以使用分组背包求解
分组背包求方案:
- 最终状态从后往前求解:找到
f[i][j]
是由f[i - 1][j - k]
的哪个条件转化而来的 - 直到找到
f[i - 1][j - k] + w[i][k]
等于f[i][j]
那么这个k
就是第i
个角色所选取的最优的值 - 同时相对的求解下一个角色选取的最优解是什么,背包的容量就要减去
k
:j -= k
;
int j = m; //背包总容量
//因为f[i][j]都是最优解
//从后往前遍历,从最后的状态计算出每个公司使用的设备数
for(int i = n;i >= 0;--i){
for(int k = 0;k <= j;++k){ //枚举组内件数(不能超过当前的背包总容量j)
if(f[i][j] == f[i - 1][j - k] + w[i][k]){
way[i] = k;
j -= k;
break;
}
}
}
c++代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 20;
int f[N][N];
int w[N][N]; //表示第i个公司选择j台时的盈利
//f[i][j]表示从前i个公司当中选,设备台数为j的所有选法的最大盈利
int way[N]; //表示第i个公司选择了i件设备
int n,m; //n表示公司数,m表示设备数
int main(){
cin >> n >> m;
for(int i = 1;i <= n;++i){
for(int u = 1;u <= m;++u) cin >> w[i][u]; //分别表示 i 个公司分配 u 台机器时的盈利
for(int j = m;j >= 0;--j){
for(int k = 0;k <= m;++k){ //枚举组内元素(注意可以不选设备也可以)
if(j >= k) f[i][j] = max(f[i][j],f[i - 1][j - k] + w[i][k]);
}
}
}
cout << f[n][m] << endl;
int j = m;
//因为f[i][j]都是最优解
//从后往前遍历,从最后的状态计算出每个公司使用的设备数
for(int i = n;i >= 0;--i){
for(int k = 0;k <= j;++k){ //枚举组内件数
if(f[i][j] == f[i - 1][j - k] + w[i][k]){
way[i] = k;
j -= k;
break;
}
}
}
for(int i = 1;i <= n;++i) cout << i << ' ' << way[i] << endl;
return 0;
}