CODEWITHSUNDEEP
algorithm
chubakueno
chubakueno

Reputation: 565

Partitioning floating-point array

While writing code, i found the following problem, to state it in a simple way:

Partition an array of floats X in array A and B such that the difference between the sum of the values in A and the sum of values of B is minimized

This was part of an investigation I was doing, but I can't find a way to efficiently perform this operation.

Edit:

To answer to those who believe this is from a math contest like PE, SPOJ or homework, it is not. I just had curiosity about this when i was trying to partition an already factorized number p in the set of factors a and b such that b=a+1. If we take logs from both sides, we can show this problem is equivalent to minimize a diference of sums, but that is where i have got stuck.

Upvotes: 2

Views: 365

Answers (1)

pkuderov
pkuderov

Reputation: 3571

Just a first simple idea. Use dynamic programming methods.
I assume that this problem can be transformed to knapsack problem. You need to pick items from X (there'll be array A) to maximize sum but don't exceed (sumX - sumA) value (there'll be sum of items from array B). For algorithm to solve knapsack problem by dynamic programming approach look at wiki e.g.
This solution can be wrong, btw... but even if it'll work I'm more than sure that more efficient, elegant and short solutions exist.

Upvotes: 3

Related Questions