砝码称重

题目

3417. 砝码称重 - AcWing题库

你有一架天平和 $N$ 个砝码，这 4N$ 个砝码重量依次是 $W_1,W_2,⋅⋅⋅,W_N$。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$。

第二行包含 $N$ 个整数$W_1,W_2,W_3,⋅⋅⋅,W_N$。

输出格式

输出一个整数代表答案。

数据范围

对于 50% 的评测用例，$1≤N≤15$。
对于所有评测用例，$1≤N≤100$，$N$ 个砝码总重不超过 $10^5$。

样例：

3
1 4 6
输出
10

思路

这道题目仔细想想是一个dp问题，可以简单的推断出每个砝码都有选和不选两种状态，一般涉及这种问题的多半需要动态规划，寻找转移方程。

设$f[i,j]$代表前$i$个砝码是否能称出$j$,$0$代表不能，$1$代表能.

然后就是寻找相互的转移方程，可以分成两个途径，选第$i$个或者不选

选第$i$个：那么前$i-1$个就能称出$j+a[i]$或者$|j-a[i]|$（$j-a[i]$可能为负数，直接取绝对值）才能称出$j$

不选第$i$个：前$i - 1$个就能称出$j$

所以转移方程就可以是

$f[i,j]=f[i-1,j] \cup f[i-1,j+a[i]] \cup f[i-1, |j-a[i]| ]$

然后最后遍历一下$fn,i$，记录一下能称出的次数就解决了。

代码

import java.util.*;

public class Main
{
    static int n, sum = 0, ans = 0;
    final static int N = 200010;
    static int[] a = new int[110];
    static boolean[][] dp = new boolean[110][N];
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            a[i] = inScanner.nextInt();
            sum += a[i];
        }
        dp[0][0] = true;
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 0; j <= sum; j ++)
            {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j + a[i]] || dp[i - 1][Math.abs(j - a[i])];
            }
        }
        for(int i = 1; i <= sum; i ++)
            if(dp[n][i])
                ans ++;
        inScanner.close();
        System.out.println(ans);
    }
}