UVa 10664

From Algorithmist
Jump to navigation Jump to search

10664 - Luggage[edit]

Summary[edit]

There is a list of luggage (defined by their weights) and you are trying to split them among 2 cars exactly equally,

print "YES" if you can, "NO" otherwise

Explanation[edit]

This problem can be solving using dp,

You run a dp algo trying to get the maximum value <= 1/2 sum of all weights

if the maximum value is equal to 1/2 the sum then print "YES" otherwise print "NO"


int dp(int r, int c){ // r is rem, c is current element
 if(mem[r][c] != -1) return mem[r][c];
 int mx = 0, t;
 for(int i = c; i < n; i++){
   if(arr[i] <= r){
     t = arr[i] + dp(r-arr[i], i+1);
     if(mx < t) mx = t;
   }
 }
 mem[r][c] = mx;
 return mem[r][c];
}
int main(){
.
.
.
 if(sum % 2 == 1) cout << "NO" << endl;
 else if(dp(sum/2, 0) == sum/2) cout << "YES" << endl;
 else cout << "NO" << endl;
.
}

Input[edit]

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

Output[edit]

NO
YES
YES


Solution[edit]