动态规划：砝码称重（01背包-闫氏DP分析法）

动态规划：砝码称重（01背包-闫氏DP分析法）

砝码称重

www.acwing.com/problem/content/3420/

DP:

• 状态表示：f[i][j]​

  • 集合：只用前 $i$ 个砝码，测出重量为 $j$ 的所有方案
  • 属性：bool

• 状态计算：$f[i][j]=f[i-1][j]||f[i-1][j-w[i]]$

对于本题，由于砝码可以放在天平两侧，可以将一个砝码拆为一正一负，用来表示放在天平的哪一侧，最后统计大于 0 的部分即可

实现方式有两种：

1. 分开 DP，需要改变遍历顺序（仅一维的情况，二维不需要考虑），因为当 w[i]​ 为负数时，要获取上一层的数据应该从小到大（和 w[i]​ 为正数时相反）
2. 构造一个大数组，设定一个基准 $B$ 作为零度线，这样就将负数和正数的组成方案全部放在同一个数组中，最后只要统计大于 $B$ 的结果即可

import java.util.*;public class Main {static final int N = 200010;static int[] w = new int[N];static boolean[] f = new boolean[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int sum = 0;for (int i = 1; i <= n; i++) {w[i] = sc.nextInt();w[i + n] = -w[i];sum += w[i];}// dp砝码全放一侧f[0] = true;for (int i = 1; i <= n; i++) {for (int j = sum; j >= 0; j--) {if (j - w[i] >= 0) {f[j] = f[j] || f[j - w[i]];}}}// dp砝码放两侧，遍历顺序不同for (int i = n + 1; i <= 2 * n; i++) {for (int j = 0; j <= sum; j++) {// 此时w[i]均为负数f[j] = f[j] || f[j - w[i]];}}int count = 0;for (int i = 1; i <= sum; i++) {if (f[i]) {count++;}}System.out.println(count);}
}