首爾性愛美術館18禁的藝術金豪禮★拿現金最實在!法人:14檔今年本業虧定了24天後重啟院會 兩岸...
2012-02-27 09:20:37 人氣(350) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 10664 - Luggage

0
收藏
0
推薦


  Luggage  

 

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 

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.

 

Sample Input 

3
1 2 1 2 1
2 3 4 1 2 5 10 50 3 50
3 5 2 7 1 7 5 2 8 9 1 25 15 8 3 1 38 45 8 1

Sample Output 

NO
YES
YES

做法 : DP背包問題
C++ 切割數字

#include <stdio.h>
#include <sstream>
#include <iostream>
using namespace std;
int main() {
string line;
int T;
scanf("%d", &T);
getchar();
while(T--) {
getline(cin, line);
istringstream in(line);
int A[30], n = 0, sum = 0;
int i, j, DP[201] = {};
while(in>>A[n])
sum += A[n], n++;
DP[0] = 1;
if(sum%2 == 0) {
sum /= 2;
for(i = 0; i < n; i++) {
for(j = sum; j >= A[i]; j--) {
if(DP[j-A[i]]) {
DP[j] = 1;
}
}
}
}
if(DP[sum] == 1) puts("YES");
else puts("NO");
}
return 0;
}
 

10664Luggage
台長:Morris
人氣(350) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 10616 - Divisible Group Sums
此分類上一篇:[UVA] 10130 - SuperSale

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文