
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 30th, 2009, 12:53 AM  #1 
Newbie Joined: Mar 2009 Posts: 2 Thanks: 0  Divide set of numbers into 2 sets
Howdy, I'm trying to solve this problem, but can't seem to make much progress. Given a set of positive numbers, divide it into 2 sets (which differ in size by 1, at max) so that the difference of their sums is minimum. So, for e.g., given the following set: [8, 4, 25, 17], the possible combinations are:
Thanks. 
March 30th, 2009, 10:01 AM  #2 
Senior Member Joined: Nov 2007 Posts: 258 Thanks: 0  Re: Divide set of numbers into 2 sets
You are looking for an algorithm?

March 30th, 2009, 12:10 PM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Divide set of numbers into 2 sets
It's NPhard. Google for 'knapsack problem'.

March 30th, 2009, 10:12 PM  #4 
Newbie Joined: Mar 2009 Posts: 2 Thanks: 0  Re: Divide set of numbers into 2 sets
Thanks CRGreathouse! I was looking for such a hint. mathmagic 
March 31st, 2009, 06:22 AM  #5 
Senior Member Joined: Oct 2008 Posts: 215 Thanks: 0  Re: Divide set of numbers into 2 sets
Given the sum of all integers in the set are S and number of elements is n, we could solve the problem by dynamic programming in O(n*S) There're total n steps in the dynamic programming, in step k, we need to find out the set of sum of any subset of the first k elements of the input set. S_k so S_1={0,a_1} S_{k+1}=S_k Union {x+a_{k+1}  for any x in S_k} 

Tags 
divide, numbers, set, sets 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Splitting prime numbers in 2 sets  Mouhaha  Number Theory  41  June 13th, 2017 05:44 AM 
Divide The Numbers  K Sengupta  Elementary Math  5  September 27th, 2015 01:37 AM 
Module divide numbers  PanTau29  Abstract Algebra  2  June 18th, 2013 06:50 AM 
Numbers as sums of special sets of integers  CRGreathouse  Number Theory  1  September 11th, 2008 04:34 PM 
natural numbers from sets....not very natural  jinjouk  Number Theory  12  June 3rd, 2008 07:11 AM 