Balance[DP]

POJ 1837

题目来源: POJ

分析

题目给出了C个"hook",要求将G个砝码挂在这些"hook"上，使得最后整个杠杆是平衡的。砝码必须被全部使用，但是"hook"不一定要全部挂有砝码。因为题目给出的数据范围较小，$2 C $,$2 \leq G \leq 20$, "hook"的坐标为$[-15,15]$。并且很明显，这个问题也是一个多段决策问题: G个砝码时的答案可以由G-1个时推理而来，并且也满足最优子结构和无后效性。所以我们使用动态规划来解决此问题。

那么我们首先就需要来确定DP方程。我们最终需要的答案是方案数, 而影响方案数的变量为砝码数量，平衡点位置。也就是说，我们可以建立一个二维的DP方程。f[][],一维存放砝码数量，一位存放平衡点的位置。在这里，平衡位置指的是$\sum_{(i,j)} w_i \times h_j$,而不是物理上实际的平衡位置。

然后我们便需要确立转移方程。这个是较为显然的，当前砝码数的方案数等于其减去上一个砝码在不同"hook"上的情况的方案数的和(下面w[]表示砝码重量，h[]表示"hook"位置):

\[ f_{i,j} = \sum_{k=1}^C f_{i-1,j-(w_{i-1}\times h_k)} \]

然后注意因为平衡位置j可能为负数，所以加上一个基数即可。

代码

#include <iostream>

using namespace std;

int f[22][2010];
int h[22], a[22];

int main()
{
trueint c,g;
truecin >> c >> g;

truefor (int i = 0; i<c; i++)
truetruecin >> h[i];

truefor (int i = 1; i<=g; i++)
truetruecin >> a[i];

truef[0][1000] = 1;
truefor (int i = 1; i<=g; i++)
truetruefor (int j = -1000; j<=1000; j++)
truetruetruefor (int k = 0; k<c; k++)
truetruetrue{
truetruetruetrueif (j-h[k]*a[i]>=-1000 && j-h[k]*a[i]<=1000)
truetruetruetruetruef[i][j+1000] += f[i-1][j-h[k]*a[i]+1000];
truetruetruetrue//if (f[i][j+1000]>0)
truetruetruetrue//	cout << i << " " << j << " " << f[i][j+1000] << endl;
truetruetrue}

truecout << f[g][1000] << endl;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。