2

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.

Improve this question
7
  • 4
    An investigation into what? This week's homework? Commented Jun 28, 2013 at 23:58
  • Looks like variant of subset sum problem. Commented Jun 29, 2013 at 0:04
  • No, not really. I was trying to partition a number in its prime factors and then reorder them so that i find two consecutives numbers a and b. It has nothing to do with homework, just curiosity. Commented Jun 29, 2013 at 0:14
  • Also, it is not from a math-programming contest like PE, SPOJ, or any other. Commented Jun 29, 2013 at 0:14
  • 1
    This is just Partition Problem (en.wikipedia.org/wiki/Partition_problem) re-stated as an optimization problem. Commented Jun 29, 2013 at 1:24

1 Answer 1

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I will give a try to those algorithms, and see how it develops. Thanks.
My last question: If i search incrementally, each time adding one factor of p (in this case, adding one element to the array), is there an optimized knapsack algorithm for this?
@chubakueno I honestly exactly don't know and if I understand you right there's no optimal incremental [by factors] strategy, imo. I think the best way to use smth like "Meet-in-the-middle" method from "Knapsack problem" wiki page. And don't expect optimal algorithms for NP-complete problem :) And keep in mind there're good approximate algorithms - maybe you don't need precise answer and "good in average" will be enough?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.