POJ1837 01背包

题目

　　大意是有一个“特殊”的天平，天平在不同位置分布着C(\(2\le C\le 20\))个挂钩，挂钩的位置坐标从-15到+15（-代表左臂，+代表右臂）。你有G(\(2\le G\le 20\))个砝码，砝码质量从1到25。问给定C个挂钩的位置坐标，G个砝码的质量，你有多少种悬挂方式使得天平平衡。

Sample Input

2 4
-2 3
3 4 5 8

Sample Output

　　有2种悬挂方式如下：
\[\begin{equation}(-2) * (3 + 4 + 5) + (3) * (8) = 0\quad or \quad(-2) * (4 + 8) + (3) * (3 + 5) = 0\end{equation}\]

算法思路

　　借鉴01背包的思想，本题中的砝码可以类比01背包中的物品，本题中将砝码挂到天平的挂钩上类比01背包中将物品放入背包中。01背包的状态定义：opt[i][j]表示前i件物品放入容量为j的背包中可以获得的最大价值，本题类似，opt[i][j]种，i可以表示前i个砝码，那么本题中j代表什么？这一点说不好想还真是不好想，如果动态规划比较熟可能比较容易想出来。仔细观察本题，题目要求有多少种悬挂方式使天平“平衡”，平衡即如式(1)所示，即所有砝码质量乘对应挂钩的位置坐标的和等于零，而我们可以把这个“和”定义为j，那么opt[i][j]即表示前i个砝码悬挂到天平上，导致“和”为j可能的悬挂方式有多少种。进而可以推导出递推公式：
\[\begin{equation}opt[i][j+hooks[k] * weights[i]] = opt[i][j+hooks[k] * weights[i]] + opt[i - 1][j]\end{equation}\]
\(hooks[k]\)表示第k个挂钩的坐标，\(weight[i]\)表示第i个砝码的质量，式(2)简单地说，当你把砝码i悬挂在挂钩k上时，“和”会由j变为\(opt[i][j+hooks[k] * weights[i]]\)，则前i个砝码导致“和”为\(j+hooks[k] * weights[i]\)的悬挂方式增多了\(opt[i - 1][j]\)种。而当你准备要放第i个砝码时，你可以悬挂在任意一个挂钩上，所以\(1\le k\le C\)。

　　另外，由题目的输入限制，可以确定j的范围为：\(-15\times20\times25=-7500\le 7500=j\le15\times20\times25\)，j的范围包含负数，但是opt数组下标索引不允许出现负数，所以把j的范围向右平移7500，则范围变为\(0\le j \le 15000\)。题目初始化时，opt[0][7500]为0，最终输出结果为opt[g][7500]，即表示放了g个砝码，“和”没有变化，即仍然保持未放砝码的状态，即平衡状态。

代码

朴素实现

Result: 1460kB, 47ms.

#include <stdio.h>
#include <iostream>

int c, g;
int hooks[20 + 5], weights[20 + 5];
int opt[20 + 5][15000 + 5];//最大右偏20*25*15=7500,最大左偏-7500。由于数组下标不能索引负数，整体向右偏移7500，得0-15000
int main() {
    scanf("%d %d", &c, &g);
    for (int i = 1; i <= c; i++)
        scanf("%d", &hooks[i]);
    for (int i = 1; i <= g; i++)
        scanf("%d", &weights[i]);
    opt[0][7500] = 1;//初始时，0件砝码是平衡的。
    for (int i = 1; i <= g; i++)
        for(int j = 0; j <= 15000; j++)//遍历所有可能出现的“和”
            if(opt[i - 1][j])
                for (int k = 1; k <= c; k++)
                    opt[i][j + hooks[k] * weights[i]] += opt[i - 1][j];
    printf("%d\n", opt[g][7500]);
}

优化一下j的循环次数

Result: 936kB, 16ms

#include <stdio.h>
#include <iostream>
#include <limits.h>

int c, g;
int hooks[20 + 5], weights[20 + 5];
int opt[20 + 5][15000 + 5];//最大右偏20*25*15=7500,最大左偏-7500。由于数组下标不能索引负数，整体向右偏移7500，得0-15000
int main() {
    scanf("%d %d", &c, &g);
    scanf("%d", &hooks[1]);
    int min_hook = hooks[1], max_hook = min_hook;
    for (int i = 2; i <= c; i++) {//找出最小的位置坐标和最大的位置坐标
        scanf("%d", &hooks[i]);
        if (hooks[i] < min_hook)
            min_hook = hooks[i];
        else if (hooks[i] > max_hook)
            max_hook = hooks[i];
    }
    int sum_weight = 0;
    for (int i = 1; i <= g; i++) {
        scanf("%d", &weights[i]);
        sum_weight += weights[i];//砝码质量和
    }

    opt[0][7500] = 1;//初始时，0件砝码是平衡的。
    for (int i = 1; i <= g; i++)
        for (int j = 7500 + sum_weight * min_hook; j <= 7500 + sum_weight * max_hook; j++)//j的遍历范围从所有砝码放在min_hook到所有砝码放在max_hook
            if (opt[i - 1][j])
                for (int k = 1; k <= c; k++)
                    opt[i][j + hooks[k] * weights[i]] += opt[i - 1][j];
    printf("%d\n", opt[g][7500]);
}