Answered Question

palma

M$3 April 20, 2009 04:22 PM

Given a random series of x's, y's, and z's, where xLTyLTz (the value of each is free), create groups of 1-5 elements of approx. equal sum.

Given a random series of x's, y's, and z's, where x less than y less than z (the value of each is free), create groups of 1-5 elements of approx. equal sum.

This must be a common problem. What would be the computational approach? You can assume the ratio of x:y:z is about 1:3:5, but it can vary somewhat to achieve groups of approx. equal sum. Input is something like "x y y y x z z y x z y x" and output could be "(x y y) (y x z) (z y) (x z) (y x)" for example. Also, the sum of the last group is unimportant, but cannot exceed the target sum.

Interesting Question? Yes (0) No (0)

RSS

Best Answer Chosen by Asker

rickg

April 20, 2009 05:34 PM

I'd start by summing the entire sequence. Call the sum S. The number of chunks you will divide sequence into is clearly less than the number of elements in the sequence. Suppose the sequence has length N. Start with N. Then the sum of each chunk should be around S/N. That'll only really work if every element is the same, so try getting to a sum of abould S/(N-1). Walk the sequence, trying to get a group of that sum, then move along, grouping as you go.

Repeat until you get to a reasonable/best answer.

This isn't a complete algorithm, but it might be a reasonable way to start.

Asker's Rating:

Helpful Answer?

(1)

(0)

Helpful: palma

Tip rickg for this answer

Permalink | Report

Answer this Question

Ask a Question

Top of Page

Buy Mahalo Dollars with Credit Card or PayPal

Top Members

This Week All Time

buddawiggi
2nd Degree Black Belt
27543 Points
M$789.91 Earned
opher
Purple Belt
4443 Points
M$196.22 Earned
annelisle
Purple Belt
2997 Points
M$91.22 Earned

See All

Most Popular Tags

mahalo(1615)

twitter(951)

iphone(465)

music(459)

google(357)

food(321)

internet(305)

online(295)

beer(279)

money(262)

facebook(255)

movies(255)

apple(251)

aotd(235)

answers(225)

health(219)

video(207)

free(205)

dog(205)

windows(197)

See All

Welcome New Members

margiec, November 29, 2009 03:20 AM
blueboy, November 29, 2009 03:12 AM
susanschultz, November 29, 2009 03:10 AM
micahbethernuge..., November 29, 2009 03:08 AM
sevenisyellow, November 29, 2009 02:34 AM

Mahalo Dollars are the currency of Mahalo Answers.

Each Mahalo Dollar costs $1.

Once you earn more than 40 Mahalo Dollars, you can request to be paid via PayPal. Each Mahalo Dollar is currently worth $0.75 when paid out via PayPal. Learn More