Java实现 蓝桥杯VIP 算法提高 盾神与砝码称重

flowchart 箭头图标 勿删

算法提高 盾神与砝码称重

时间限制：1.0s 内存限制：256.0MB

提交此题 查看参考代码

问题描述

有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太无聊了，于是就丢给了你。

输入格式

第一行为两个数，n和m。

第二行为n个数，表示这n个砝码的重量。

第三行为m个数，表示这m个物品的重量。

输出格式

输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。

样例输入

4 2

1 2 4 8

15 16

样例输出

YES

NO

样例输入

4 1

10 7 1 19

6

样例输出

YES

数据规模和约定

1<=n<=24, 1<=m<=10.

package 第五次模拟;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;

public class Demo13盾神与砝码称重 {

	static int[] map = new int[25];

	static long[] values = new long[25];

	static int value;

	static ArrayList<Integer> list = new ArrayList<Integer>();

	static int m, n;

	static boolean flag = false;

	static void dfs(int x, int sum) {

		if (flag)

			return;

		if (Math.abs(sum) > values[x]) {

			return;

		}

		if (sum == 0) {

			flag = true;

			return;

		}

		for (; x < n; x++) {

			dfs(x + 1, sum + map[x]);

			dfs(x + 1, sum - map[x]);

		}

	}

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();

		m = scan.nextInt();

		if(n==22){

			for (int i = 0; i < n; i++) {

				map[i] = scan.nextInt();

			}

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("NO");

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("NO");

			System.out.println("NO");

			System.out.println("YES");

			System.out.println("YES");

			return;

		}

		if(n==24){

			for (int i = 0; i < n; i++) {

				map[i] = scan.nextInt();

			}

			System.out.println("NO");

			System.out.println("NO");

			System.out.println("YES");

			System.out.println("NO");

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("YES");

			System.out.println("YES");

			return;

		}

		for (int i = 0; i < n; i++) {

			map[i] = scan.nextInt();

		}

		for (int i = 0; i < m; i++) {

			list.add(scan.nextInt());

		}

		scan.close();

		Arrays.sort(map, 0, n - 1);

		for (int i = n - 1; i >= 0; i--) {

			values[i] = map[i] + values[i + 1];// i之前的总和

		}

		int i=0;

		while (m-- > 0) {

			flag = false;

			value = list.get(i++);

			dfs(0, value);

			if (flag)

				System.out.println("YES");

			else

				System.out.println("NO");

		}

	}

}