ACM Plan UVa - 10664 Luggage（动态规划）

题意

给出n个(n <= 20)物品的重量, 问这堆物品能否划分为重量相同的两堆。

解题

典型的动态规划题目，求子集元素和。将给出的数据同时视为物品的重量和价值，输入时计算所有重量和sum。然后dp求出不同重量下能得到的最大物品价值，最后判断sum - 2 * dp[sum / 2] 是否为0即可。

AC-Code

#include <cstdio>
#include <cstring>
int dp[210];
int v[21];
int main(){
    // freopen("i.txt", "r", stdin);// freopen("o.txt", "w", stdout);int t; scanf("%d", &t);getchar();while(t--){
    int num, sum = 0, cnt = 0;char c;while(scanf("%d%c", &num, &c)){
    v[cnt++] = num;sum += num;if(c == '\n') break;}memset(dp, 0, sizeof(dp));for(int i = 0; i < cnt; i++)for(int j = sum / 2; j >= v[i]; j--)if(dp[j] < dp[j - v[i]] + v[i])dp[j] = dp[j - v[i]] + v[i];puts((sum - 2 * dp[sum / 2] == 0)? "YES" : "NO");}
}