算法提高 盾神与砝码称重
时间限制：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");
}
}
}