My Math Forum Divide set of numbers into 2 sets
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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: [8,4] & [25,17] - 30 [8,25] & [4,17] - 12 [8,17] & [4,25] - 4 Clearly, the answer is [color=#FF4000][4, 25] & [8, 17][/color]. 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 NP-hard. 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Mouhaha Number Theory 41 June 13th, 2017 05:44 AM K Sengupta Elementary Math 5 September 27th, 2015 01:37 AM PanTau29 Abstract Algebra 2 June 18th, 2013 06:50 AM CRGreathouse Number Theory 1 September 11th, 2008 04:34 PM jinjouk Number Theory 12 June 3rd, 2008 07:11 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top