|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
October 10th, 2003, 08:46 PM
|
|||
|
|||
Closest Sum
This is NOT a school problem, just some program I'm writing to help me organize my files (putting them on CDRs)
Problem: Given a set of integers (eg filesizes in a directory), a target number (eg max size a CDR can hold), and the given set of integers’ sum is always greater than or equal to the target number. Find a subset of the given integers such that their sum equals to or is closest to the target number. However, it Cannot be greater than the target number (overburn isn't good for your burner). If there is a tie, in another word, there are two or more subsets of integers that give the same sum which is either closest to, or equal to the target number, display just one of those sets. Example 1: Input Integers: 240, 593, 539, 23, 687, 43, 80 Target Number: 2059 Output 240, 593, 539, 687 Example 2: Input: Integers: 320, 594, 339 Target Number: 680 Output 320, 339 Can this be solved without using a brute force method? Thanks in advance!
|
|
#2
October 11th, 2003, 08:02 AM
|
|||
|
|||
|
nevermind this.... I just found out there's no known algorithm for this... it's a NP-complete problem LOL! anyone who can solve this can get a nobel price or something :P
|
|
#3
October 13th, 2003, 01:45 AM
|
||||
|
||||
|
How about using this method:
1. Let's call the max capacity as A 2. Arrange the size of the files in descending order and note down the smallest element size. 3. Pick the first element in the array (i.e.) the largest size. Let's call this number B 4a. If (A - B) > (size of smallest element), then pick B, subtract B from A and repeat step 3 for the next element in the array. 4b. If (A - B) < (size of smallest element) AND (sum of smaller elements) > B, then reject B and go to the next element in the array. 4c. If (A - B) < (size of smallest element) AND (sum of smaller elements) <= B, then pick B, subtract B from A and repeat step 3 for the next element. 4d. If A < B, then reject B and repeat step 3 for the next element 5 Continue step 3 until there are no more elements in the array. To see how this works, lets consider both cases: Example 1. Target Number = 2059 Therefore, A = 2059 originally Array is 687, 593, 539, 240, 80, 43, 23 from step 2 and smallest element is 23 B = 687 (from step 3) A - B = 2059 - 687 = 1372, which is > 23, so we pick B = 687 from rule 4a. Now A = 1372 and we repeat step 3 and get B = 593 Now A - B = 1372 - 593 = 779, which is > 23, so we again pick B = 593, by rule 4a. Now A = 779 and B = 539 from repeating step 3 A - B = 779 - 539 = 240, which is > 23, so we pick B = 539 Now A = 240 and B = 240 from step 3. A - B = 240 - 240 = 0 which is < 23. So we compute the sum of smaller elements (23 + 43 + 80 = 146) and find that it is less than B (240). Hence, by rule 4c, we accept B and subtract B from A. Now A is 0. Now for 80, 43 and 23, we reject them all by rule 4d Thus we picked 687, 593, 539 and 240 Example 2. A = 680 Array is 594, 339, 320 from step 2 and 320 is smallest element. Now B = 594 initially A - B = 86, which is < 320. So we compute sum of smaller elements (339 + 320 = 659). Now (sum of smaller elements) > B, hence by rule 4b, we reject B and go to the next element. Now A = 680 and B = 339 from step 3. A - B = 341, which is > 320. Hence, by rule 4a, we pick B and set A = 341 Now A = 341 and B = 320 from step 3. A - B = 21, which is > 320. Now (sum of smaller elements = 0) is < B (320) So we pick B by rule 4c. Now A = 21 and we have no more elements, so we quit searching by rule 5. Numbers picked are 339 and 320 I'll take that (Ig)Nobel prize by Express Mail please  .
__________________
Up the Irons What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home. "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest Down with Sharon Osbourne Puzzle of the Month solved by Keath and KevinADC, superior perl programmers of the month Last edited by Scorpions4ever : October 13th, 2003 at 01:48 AM.
|
|
#4
October 13th, 2003, 04:34 PM
|
|||
|
|||
Close but no cigar....
yeah you got it to work with the 2 simple examples I gave... but, if you try this:
267,493,869,961,1000,1153,1246,1598,1766,1922. Target=5842 then your method doesn't work... they don't pay $1M for something you can figure out over a weekend thanks for trying tho 
|
|
#5
October 13th, 2003, 04:54 PM
|
||||
|
||||
|
Good call
There goes my chance at making $1M
|
|
#6
October 13th, 2003, 05:38 PM
|
||||
|
||||
|
When the going gets tough, the tough use brute force, so here's my brute force technique
.1. Build an array of all possible sizes. 2. Scan the above array to generate all possible combinations and their sums into two separate arrays. 3. Go thru the array of sums and compute the difference between max size and each of the sums and pick the one which is >= 0 and is the least difference. 4. From step 3, you've found the combination which comes closest to to the total. So print out the results. I went ahead and coded the whole thing in python (the program ends up 37 lines long, including whitespace and comments!): Code:
#!/usr/bin/env python
# Adjust globarray and max_sum as needed.
globarray = [267,493,869,961,1000,1153,1246,1598,1766,1922]
max_sum = 5842
globsum = []
globcombo = []
# Function to generate all combinations
def generate_combos(prefix, start, sum):
global globarray
global globsum
global globcombo
for i in range(start, len(globarray)):
string = prefix + str(globarray[i]) + ' '
newsum = sum + globarray[i]
# Add new entry to global arrays and recurse further
globsum.append(newsum)
globcombo.append(string)
generate_combos(string, i+1, newsum)
# Generate all combinations of globarray
generate_combos('', 0, 0)
# Now find the minimum difference and its position
max_diff = max_sum
ind = -1
for i in range(0, len(globsum)):
diff = max_sum - globsum[i]
if (diff >= 0 and diff < max_diff):
max_diff = diff
ind = i
# Now print the winning combo
print "The best combo is ", globcombo[ind], "= ", globsum[ind]
print "Done\n";
This code seems to work for all 3 cases that you presented. Of course, it is a brute force technique rather than an elegant algorithm, but I'd love to see a list that it doesn't work with Last edited by Scorpions4ever : October 13th, 2003 at 05:41 PM.
|
|
#7
October 14th, 2003, 01:39 AM
|
|||
|
|||
|
Yeah... that's like the only way to solve this problem. but as we all know... combination get HUGE when n gets big... it'll work for all list...the question is How LONG it would take to scan a list of 100 numbers (eg 100C50, it'll take forever).
I've a good class for combination, which will return the combination indexes, so I can use it for many problems that I can't come up with a good algorightm.... I use it alot coz I can't really think of good algorithms hehehe However, since this app that I'm planning to build will usually involves a lot of Directory Size (ie the integers in the list) maybe > 100 directories.... so brute force isn't an option... .... well.... thanks for your time for trying to help me solve an unsolveable problem
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Closest Sum |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
