问题描述
有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太无聊了，于是就丢给了你。
输入格式
第一行为两个数，n和m。
第二行为n个数，表示这n个砝码的重量。
第三行为m个数，表示这m个物品的重量。
第二行为n个数，表示这n个砝码的重量。
第三行为m个数，表示这m个物品的重量。
输出格式
输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。
样例输入
4 2
1 2 4 8
15 16
1 2 4 8
15 16
样例输出
YES
NO
NO
样例输入
4 1
10 7 1 19
6
10 7 1 19
6
样例输出
YES
数据规模和约定
1<=n<=24, 1<=m<=10.
PS：
1.cmp()是快排函数中需要调用的比较函数，也就是次排序应如何排（如是从大大小还是从小到大），此函数可缺省，也可自己写。
2.在这句话里 a，b肯定是一个指针变量,(int *)a是表示把a强制转换成一个int型的指针。如果以前a是char型，编译器会认为a指向的那一个字节的内存单元是a里面的东西把a转换成int型，编译器会认为a指向的连续四个字节里的东西都是a里面的。*(int *)a就是取a指向的内容的意思，跟*a的那个*作用一样。
#include
#include
int n, m;
int weight[25];
int sum[25];
int cmp(const void* a, const void* b)
{
return *((int*)b) - *((int*)a);
}
int DFS(int weigh, int i)
{
if (weigh==0) //weigh等于0时，返回值为真
{
return 1;
}
if (abs(weigh)>sum[i]) //物品重量大于所有砝码相加之和时，
返回值为假
{
return 0;
}
{
if (DFS(weigh-weight[i], i+1) || DFS(weigh+weight[i],
i+1) || DFS(weigh, i+1))
{
return 1; //反正随便凑，使等式两边相
等就行
}
}
return 0;
}
int main(void)
{
int o;
int i;
scanf("%d%d", &n, &m);
for (i=0; i
=0; --i)
{
sum[i] = sum[i+1] + weight[i]; //回溯
}
for (i=0; i
版权声明：本文为weixin_40061167原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。