HDOJ5616 Jam‘s balance

HDOJ5616 Jam’s balance

题目描述

背景

有$N$个已知质量的砝码，分别询问给出的$M$个质量能否被称出

输入

1. 第一行输入一个变量$T$，表示有$T$组数据；
2. 第二行输入一个变量$N$，表示有$N$个砝码；
3. 第三行输入$N$个变量$w_1,w_2,\cdots ,w_n$，分别表示这$N$个砝码的质量；
4. 第四行输入一个变量$M$，表示要询问的质量有$M$个；
5. 第五行输入$M$个变量$u_1,u_2,\cdots ,u_m$，分别表示要询问的质量

输出

对于每组数据每个询问的质量判断并输出一行$YES$或$NO$

题解

解法一

定义一个数组$f[]$，$f[i]$表示当表示出的质量小于等于$i$时所能表示的最大值，那么本题就可以看成是一个背包问题，而且是每个物品的体积和价值都一致的背包问题
背包问题的状态转移方程是$f[j]=max(f[j],f[j-v[i]]+w[i])$，该问题中即为$f[j]=max(f[j],f[j-w[i]]+w[i])$，但是该问题有一些不同，因为砝码可以放在两边，所以不是简单的价值相加，但是考虑用$w[i]$加上前$i-1$个砝码组合出的某个方案时还是可以使用这个方程的
现在考虑相减的情况，假设要用第$i$个砝码更新$f[j]$，那么对第$i$个砝码的使用有两种情况，一是用前$i-1$个砝码组合出的某个方案减去$w[i]$，二是用$w[i]$减去前$i-1$个砝码组合出的某个方案
第一种情况和相加类似，易得$f[j]=max(f[j],f[j+w[i]]-w[i])$，但是为了防止$f[k](k>j)$比$f[j]$更先更新，从而导致同一砝码使用两次，$j$应该顺序枚举
第二种情况使用$w[i]$更新时，由于$f[j]$表示的是不大于$j$的最大值，所以应该用$w[i]$减去不小于$w[i]-j$的最小值，那么还需要再定义一个数组$g[]$，$g[i]$表示当表示出的质量大于等于$i$时所能表示的最小值，于是可以得到方程$f[j]=max(f[j],w[i]-g[w[i]-j])$
定义了一个新的数组，那么它也需要被维护，方程和$f$是类似的
接着考虑到实际上只需要判断是否可以得到询问的质量，而不需要真正算出最大值和最小值，所以$f,g$都可以换为$bool$数组并对方程做出改变
最后考虑相加和两种相减计算的先后顺序，相加第一个，之后无论是何种相减，即使减去的方案中使用了同一砝码也会抵消，第二个是相减的情况二，这样在考虑相减的情况一时遇到同一砝码也会抵消，如果后两者反过来，则会导致统一砝码使用多次
代码如下：

#include<cstdio>
#include<cstring>
using namespace std;

const int M = 25;
const int N = 2005;

int main() {
    int t, n, m, mxx, sum;
    int w[M], v[N];
    bool f[N], g[N];

    scanf("%d", &t);

    while(t--) {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        g[0] = 0;

        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i) scanf("%d", &v[i]);

        sum = w[1];
        g[w[1]] = f[w[1]] = g[0] = f[0] = 1;     //初始化不要忘记改了

        for(int i = 2; i <= n; ++i) {
            for(int j = sum += w[i]; j > w[i]; --j) {
                f[j] |= f[j - w[i]];
                g[j] |= g[j - w[i]];
            }
            for(int j = 1; j <= w[i]; ++j) {
                f[j] |= g[w[i] - j];
                g[j] |= f[w[i] - j];
            }
            for(int j = 1, mx = sum - (w[i] << 1); j <= mx; ++j) {
                f[j] |= f[j + w[i]];
                g[j] |= g[j + w[i]];
            }
        }

        for(int i = 1; i <= m; ++i) f[v[i]] ? puts("YES") : puts("NO");
    }
    return 0;
}

解法二

接下来考虑是否可以把两种相减变成一种，核心想法还是背包问题的解法
可以考虑把相加和相减分成两个循环，先单纯考虑相加，再用方案减去$w[i]$的方式对方案进行更新，这样就同时考虑了两种相减
代码如下：

#include<cstdio>
#include<cstring>
using namespace std;

#define il inline

const int M = 25;
const int N = 2005;

int main() {
    bool f[N];
    int t, n, m, sum;
    int w[M];

    scanf("%d", &t);

    while(t--) {
        memset(f, 0, sizeof(f));
        sum = 0, f[0] = 1;

        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);

        for(int i = 1; i <= n; ++i) {
            for(int j = sum + w[i]; j >= w[i]; --j) f[j] |= f[j - w[i]];
            sum += w[i];
        }

        for(int i = 1; i <= n; ++i) {
            int mx = sum - w[i];
            for(int j = 1; j <= mx; ++j) f[j] |= f[j + w[i]];
        }

        scanf("%d", &m);
        while(m--) {
            int x;
            scanf("%d", &x);
            f[x] ? puts("YES") : puts("NO");
        }
    }
    return 0;
}

优化

当同质量的砝码有多个时，如果看成单独的多个砝码，某些本质相同的操作会重复进行，所以不妨看成多重背包再进行二进制优化，二进制优化就是把有多个的某质量砝码依据二进制进行分组等效，如把$8$个质量为$1$的砝码等效质量分别为$1,2,4,1$的$4$个砝码，等效前后能表示的质量不变，而砝码数量却下降了
可以发现这个等效本质上就是满$3$变$1$，同时两倍质量的砝码数量加$1$，直到不再可以等效
由于可能的砝码数量只有$0,1,2$，所以不妨使用$bool$数组$s$储存砝码数量，$false,true$分别表示$1,2$，且$w[i]$表示第$i$种砝码的质量，再添加一个数组$pos[i]$表示质量为$i$的砝码在$s$中的下标，这样每当出现一个新质量的砝码，$s$中元素的总数$tot$就加$1$
由于数量较小，对于数量为$2$的砝码也可以不采用多重背包的一般方法，直接当成$2$个单独砝码处理即可
代码如下：

#include<cstdio>
#include<cstring>
using namespace std;

#define il inline

const int M = 25;
const int N = 2005;

il int read() {
    int x = 0;
    char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}

int main() {
    bool s[M], f[N];
    int t, n, m, tot, sum, wei;
    int w[M], pos[N];
    memset(pos, 0, sizeof(pos));

    t = read();

    while(t--) {
        memset(f, 0, sizeof(f));
        tot = sum = 0, f[0] = 1;

        n = read();
        for(int i = 1, j; i <= n; ++i) {
            wei = read(), j = pos[wei];
            while(j && s[j]) s[j] = 0, j = pos[wei <<= 1];
            if(!j) pos[wei] = ++tot, s[tot] = 0, w[tot] = wei;
            else s[j] = 1;
        }

        for(int i = 1; i <= tot; ++i) {
            for(int j = sum += w[i]; j >= w[i]; --j) f[j] |= f[j - w[i]];
            if(s[i]) w[++tot] = w[i], s[tot] = 0;
            pos[w[i]] = 0;     //顺便重置pos，这样就不用反复memset
        }

        for(int i = 1; i <= tot; ++i)
            for(int j = 1, mx = sum - w[i]; j <= mx; ++j)
            	f[j] |= f[j + w[i]];

        m = read();
        while(m--) f[read()] ? puts("YES") : puts("NO");
    }
    return 0;
}

打赏

制作不易，若有帮助，欢迎打赏！