分析:
分组背包问题是互斥选择模型,即一个物品组内只能做出一种决策选择,叫做分组背包问题
分组背包问题,如果运用分组背包模型来做的话,如下转换
每个公司看成一个物品组,我们至多可以选择m个,选择0~m个操作是互斥的,只能做一个,
因此对于分给第 i 个 公司 的不同 机器数量 可以分别看作是一个 物品组 内的 物品
状态计算
初始化:全部初始化为0
状态计算:根据最后一个不同点/最后一次选择来进行划分,可以划分为以下子集
- 当前选择0个 dp[i][j]=dp[i-1][j]
- 当前选择1个 dp[i][j]=dp[i-1][j-1]
- ....
- 当前选择j个 dp[i][j]=dp[i-1][0]
由于要找出方案具体的选择,但是没有字典序的限制条件,所以可以再遍历一次,记录对于每个公司具体分配了哪些
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
int n,m;
int dp[N][N];
int w[N][N];
int way[N]; //每个公司分配了几个
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
}
cout<<dp[n][m]<<endl;
int j=m;
for(int i=n;i;i--)
for(int k=0;k<=j;k++) //由于是互斥的,每个公司只能选择一次,找出选择后break
{
if(dp[i][j]==dp[i-1][j-k]+w[i][k])
{
way[i]=k;
j-=k;
break; //做出选择后break;
}
}
for(int i=1;i<=n;i++)
cout<<i<<' '<<way[i]<<endl;
return 0;
}