My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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:
  • [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.
mathmagic is offline  
 
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?
brunojo is offline  
March 30th, 2009, 12:10 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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'.
CRGreathouse is offline  
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
mathmagic is offline  
March 31st, 2009, 06:22 AM   #5
duz
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}
duz is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2018 My Math Forum. All rights reserved.