10664 - Luggage
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1605
Peter and his friends are on holiday, so they have decided to make a trip by car to know the north of Spain. They are seven people and they think that two cars are enough for their luggage.
It’s time to leave… and a heap of suitcases are awaiting out of the cars. The drivers disagree about which suitcase must be put into each boot, because nobody wants one boot to carry more weight than the other one. Is it possible that the two boots load with the same weight? (Obviously without unpacking the suitcases!)
Consider m sets of numbers representing suitcases weights, you must decide for each one, if it is possible to distribute the suitcases into the boots, and the two boots weigh the same.
Input
The first line of the input contains an integer, m, indicating the number of test cases. For each test case, there is a line containing n integers (1<=n<=20) separated by single spaces. These integers are the weights of each suitcase. The total sum of the weights of all the suitcases is less or equal to 200 kilograms.
Output
本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45376.htm
The output consists of m lines. The i-th line corresponds with the i-th set of suitcases weight and contains the string “YES” or “NO”, depending on the possibility that the two boots load with the same weight for the respective test case.
31 2 1 2 12 3 4 1 2 5 10 50 3 503 5 2 7 1 7 5 2 8 9 1 25 15 8 3 1 38 45 8 1
NOYESYES
水一水。
完整代码：
/*0.015s*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int val[25], dp[205];
int main()
{
int t, sum, n, i, j;
char ch;
scanf("%d", &t);
while (t--)
{
sum = n = 0;
do
{
scanf("%d", &val[n]);
sum += val[n++];
ch = getchar();
}
while (ch != 10 && ch != -1);
if (sum & 1) puts("NO");
else
{
memset(dp, 0, sizeof(dp));
sum >>= 1;
for (i = 0; i < n; ++i)
for (j = sum; j >= val[i]; --j)
dp[j] = max(dp[j], dp[j - val[i]] + val[i]);
puts(dp[sum] == sum ? "YES" : "NO");
}
}
return 0;
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索for
， each
， and
， of
The
iso10664中文版、乐高10664、iso 10664、iso 10664 中文、乐高10664图纸，以便于您获取更多的相关知识。