POJ1837 Balance 背包

题目大意: 有一个天平，天平左右两边各有若干个钩子，总共有C个钩子(每个钩子有相对于中心的距离,左负右正)，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。

将每个砝码看作一组，组内各个物品的体积为每个挂钩与该砝码形成的力矩，背包总体积严格为0，这便是分组背包计数问题（特殊点：每一组必须出一个物品，而不是至多出一个物品）。由于c++不允许负的数组下标，所以每次更新时，j要加上offsetJ。

实现分组背包计数问题时，可以用填表法（找以前节点求自己值）（DP1）或刷表法（找以后节点更新以后值）（DP2）。由于刷表法时，如果DP[i][j]==0，可以跳过，所以节省时间。

注意：

不可以用一维数组倒序循环来表示DP数组，因为j-objV可能比j还大
同理，每次判断时，不是j-objV>=0，0代表天平的支点而不是左端点。所以应当为j-objV>=minJ。

#include <cstdio>

#include <cstring>

#include <cstdarg>

using namespace std;

const int MAX_V = , MAX_OBJ = , MAX_HOOP = ;

const int Plus = ;

#define Sub(x) x+offsetJ

int TotHoop;

int Len[MAX_HOOP], W[MAX_OBJ];

void _printf(char *format, ...)

{

#ifdef _DEBUG

    va_list(args);

    va_start(args, format);

    vprintf(format, args);

    va_end(args);

#endif

}

int DP1(int totHoop, int totDev, int *_w, int *_len)

{

    int minJ = , maxJ = , wSum = , offsetJ, objV = ;

    static int DP[MAX_OBJ][MAX_V];

    for (int dev = ; dev <= totDev; dev++)

        wSum += _w[dev];

    for (int hoop = ; hoop <= totHoop; hoop++)

        _len[hoop] >  ? maxJ += _len[hoop] * wSum : minJ += _len[hoop] * wSum;

    offsetJ = -minJ;

    DP[][offsetJ] = ;

    _printf("+ offsetJ %d maxJ %d\n", +offsetJ, maxJ);

    for (int i = ; i <= totDev; i++)

        for (int j = minJ; j <= maxJ; j++)

            for (int hoop = ; hoop <= totHoop; hoop++)

            {

                objV = _w[i] * _len[hoop];

                if (j - objV >= minJ && j - objV <= maxJ)

                {

                    DP[i][j + offsetJ] += DP[(i - )][j + offsetJ - objV];

                    _printf("%d=DP[%d][%d] += DP[%d][%d]=%d\n", DP[i][j + offsetJ], i, j, i - , j - _w[i] * _len[hoop], DP[i - ][j - _w[i] * _len[hoop] + offsetJ]);

                }

            }

    return DP[totDev][offsetJ];

}

int DP2(int totHoop, int totDev, int *_w, int *_len)

{

    int minJ = , maxJ = , wSum = , offsetJ, objV = ;

    static int DP[MAX_OBJ][MAX_V];

    for (int dev = ; dev <= totDev; dev++)

        wSum += _w[dev];

    for (int hoop = ; hoop <= totHoop; hoop++)

        _len[hoop] >  ? maxJ += _len[hoop] * wSum : minJ += _len[hoop] * wSum;

    offsetJ = -minJ;

    DP[][offsetJ] = ;

    _printf("+ offsetJ %d maxJ %d\n", + offsetJ, maxJ);

    for (int i = ; i < totDev; i++)

        for (int j = minJ; j <= maxJ; j++)

            if (DP[i][j+ offsetJ])

                for (int hoop = ; hoop <= totHoop; hoop++)

                {

                    objV = _w[i+] * _len[hoop];

                    DP[i + ][j + objV + offsetJ] += DP[i][j + offsetJ];

                    _printf("%d=DP[%d][%d] += DP[%d][%d]=%d\n", DP[i+][j+objV+ offsetJ], i+, j+objV+ offsetJ, i, j+ offsetJ , DP[i][j + offsetJ]);

                }

    return DP[totDev][offsetJ];

}

int main()

{

#ifdef _DEBUG

    freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

    int totDevice, vCnt = , totV = , maxV = , minV = ;

    scanf("%d%d", &TotHoop, &totDevice);

    for (int i = ; i <= TotHoop; i++)

        scanf("%d", i + Len);

    for (int i = ; i <= totDevice; i++)

        scanf("%d", i + W);

    printf("%d\n", DP2(TotHoop, totDevice, W, Len));

    return ;

}

巴特西

POJ1837 Balance 背包

最新文章

热门文章