蓝桥杯算法提高VIP-盾神与砝码称重 （Java代码）

import java.io.InputStream;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int[] w = new int[25];
	static int[] k = new int[25];
	static Scanner input = new Scanner(System.in);
	static int n = input.nextInt();
	static int m = input.nextInt();
	static int flag = 0;

	public static void main(String[] args) {
		// TODO 自动生成的方法存根

		for (int i = 0; i < n; i++) {
			w[i] = input.nextInt();

		}
		sort(w);
		for (int i = n - 1; i >= 0; i--) {
			k[i] = w[i] + k[i + 1]; // 依次求出前（n-i）个砝码能称出的最大重量
		}
		while (m-- > 0) {
			int s = input.nextInt();

			flag = 0;
			dfs(s, 0);
			if (flag == 1) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}

	}

	static void dfs(int s, int x) {
		if (flag == 1) { // 退出条件
			return;
		}

		if (s == 0) // s等于0表示称出了结果
		{
			flag = 1;
			return;
		}

		if (Math.abs(s) > k[x]) {// 如果物品的重量大于剩下的砝码能表示的最大重量
			return;
		}
		for (; x < n; x++) // 每个x表示搜索的起点
		{
			// 两种情况
			dfs(s - w[x], x + 1); // 把砝码放在天平的右边
			dfs(s + w[x], x + 1); // 把砝码放在天平的左边
		}

	}

	private static void sort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] > a[i]) {
					int t = a[j];
					a[j] = a[i];
					a[i] = t;
				}
			}
		}
	}
}

解题思路:





注意事项:





参考代码: