AcWing1013.机器分配（分组背包问题与方案记录）

这道题其实不太容易看出背后的模型。这道题本质上是一个分组背包问题。我们将每一个公司看成一组&＃xff0c;而在每一个组内&＃xff0c;将不同情况下的盈利状况看作物品的价值&＃xff0c;而得到这种利益所需的机器数目看作物品的体积。

因此&＃xff0c;这个问题就变成了&＃xff0c;从不同的组内&＃xff0c;至多选取一个物品&＃xff0c;在背包容量允许的条件下&＃xff0c;我们所能携带的最大价值。

那么这道题的其中一问就可以解决了。如果大家不懂分组背包的话&＃xff0c;建议大家去看作者之前的文章&＃xff1a;分组背包问题详解

那么第二个问题是我们今天讨论的重点&＃xff0c;即对于背包问题而言&＃xff0c;我们如何存储最优解的方案&＃xff1f;

此时我们采用拓扑图的角度来理解这个问题&＃xff0c;我们求解答案的过程就是构建拓扑图的过程。我们将每个状态看作一个点&＃xff0c;然后通过点与点之间的连接体现DP中的状态转移方程。如下图所示&＃xff1a;
A点就是我们初始化的状态&＃xff0c;当我们的得到了A点后&＃xff0c;才能够通过转移&＃xff0c;即图中的边&＃xff0c;得到状态B。

当我们算出了状态B和状态C的时候&＃xff0c;才能够通过边的连接得到状态D&＃xff0c;状态D到底是什么则需要对比由B和C转移过来的两条路线中哪个是当下的最优解&＃xff0c;当比较出最优解后&＃xff0c;我们的状态D就可以被赋值为这个最优解。

如果将上述的拓扑图看作一个动态的过程的话&＃xff0c;我们会发现这是一个从一个点不断地变成图的过程。

接下来&＃xff0c;我们利用上面的图来分析如何得到详细地方案&＃xff0c;首先我们想知道到达某个状态的方案&＃xff0c;放在这个图里&＃xff0c;即我们想知道到达一个点的路线&＃xff08;但并不是所有能到当前的点的路线都是答案&＃xff0c;我们需要在这些路线中比较出最优的&＃xff09;。

很明显&＃xff0c;我们需要先在图中定位到这个点&＃xff0c;然后观察它的入度&＃xff0c;如下图&＃xff0c;假设我们想知道到达F点的最优解的路线&＃xff1a;

单纯地看这个图的话&＃xff0c;还是比较抽象的&＃xff0c;因此我们把01背包的方程映射到这个图中&＃xff0c;&＃xff08;这里只是因为01背包比较容易映射&＃xff0c;分组背包等问题同理&＃xff09;。我们发现想要得到F状态可以通过DF和EF两个状态通过边分别转移过来。但是我们想得到的是最优的&＃xff0c;如果两个转移状态的过程是相等的&＃xff0c;即f[i-1][j-v]&＃43;w&＃61;&＃61;f[i-1][j]&＃xff0c;那么就说明这两个边都可以&＃xff08;所以我们将这两个边搞成红色&＃xff09;&＃xff0c;任意选一个边即可。

接着&＃xff0c;我们以DF这条边为例子&＃xff0c;我们还需要知道D状态怎么转化而来&＃xff0c;同理我们比较CD和BD两个转移过程&＃xff0c;发现CD是最优的&＃xff0c;那么DC就是最优解方案中的一部分。

就这样我们可以从终点逆推起点&＃xff0c;从而记录方案。

那么这道题也同理&＃xff0c;对于一个点而言&＃xff0c;可以由前一个组内的任意一个物品转移过来&＃xff0c;但是我们需要通过比较找到最优的路线。然后慢慢地逆推得到方案。

#include
#include
#include
using namespace std;
const int N&＃61;15,M&＃61;20;
int f[N][M],v[N][M],w[N][M];
int way[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)
{
scanf("%d",&w[i][j]);
v[i][j]&＃61;j;
}
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
{
for(int j&＃61;0;j<&＃61;m;j&＃43;&＃43;)
{
for(int k&＃61;0;k<&＃61;m;k&＃43;&＃43;)
{
if(j>&＃61;v[i][k])
f[i][j]&＃61;max(f[i][j],f[i-1][j-v[i][k]]&＃43;w[i][k]);
}
}
}
cout<<f[n][m]<<endl;
int j&＃61;m;
for(int i&＃61;n;i>&＃61;1;i--)
{
for(int k&＃61;0;k<&＃61;m;k&＃43;&＃43;)
{
if(j>&＃61;v[i][k]&&f[i][j]&＃61;&＃61;f[i-1][j-v[i][k]]&＃43;w[i][k])
{
way[i]&＃61;k;
j-&＃61;k;
break;
}
}
}
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)cout<<i<<" "<<way[i]<<endl;
return 0;
}