Here is a task:
"3 brothers have to transfer 9 boxes from one place to another.
These boxes weigh 1, 2, 4, 5, 6, 8, 9, 11, 14 kilos.
Every brother takes 3 boxes.
So, how to make a program that would count the most optimal way to take boxes?
The difference between one brother's carrying boxes weight and other's has to be as small as it can be."
Can you just give me an idea or write a code with any programming language you want ( php or pascal if possible? ).
Thanks.
Since this is a homework, I want to give you the opportunity to solve it yourself. As a hint, the easiest way to do this, but NOT the most efficient, is bruteforcing: http://en.wikipedia.org/wiki/Brute-force_search
Try to take all the possible combinations and find the one that minimizes the workload of the brothers.
I'll not tell either but you can also try giving the 3 biggest boxes to the three brothers. Then use any available small amounts to make them equal to the biggest ( f.e. 14). Then repeat. The easiest way would be to sum this all up and divide it by the number of the brothers to see what's the exact weight they should carry and try to arrange the packets in such way that there's no more than 1 kilo (preferably 0 ) difference.
A B C
---------------------
14 11 8
6 9 5
4
2
1
-- -- --
20 20 20
A B C
---------------------
14 11 9
1 2 4
5 6 8
-- -- --
20 19 21
A B C
---------------------
14 11 9
8 6 5
4 2 1
-- -- --
26 19 15
By using this last method (assign the heaviest box to the first brother, the second heaviest box to the second brother, the third heaviest box to the third brother, the fourth heaviest box to the first brother, and so on until there are no more boxes) your results will never be more than 34% worse than the optimal solution (20 kilos each), as you can see:
20 / 1.34 = 14.9 (minimum load = 15)
20 * 1.34 = 26.8 (maximum load = 26)
Here is a sample code in PHP:
$boxes = array(1, 2, 4, 5, 6, 8, 9, 11, 14);
$brothers = array();
rsort($boxes); // sort boxes weight (highest to lowest)
while (count($boxes) > 0)
{
$brothers['A'][] = array_shift($boxes);
$brothers['B'][] = array_shift($boxes);
$brothers['C'][] = array_shift($boxes);
}
foreach ($brothers as $key => $value)
{
$brothers[$key] = array_filter($value);
$brothers[$key]['total'] = array_sum(array_filter($value));
}
echo '<pre>';
print_r($brothers);
echo '</pre>';
And the respective output:
Array
(
[A] => Array
(
[0] => 14
[1] => 8
[2] => 4
[total] => 26
)
[B] => Array
(
[0] => 11
[1] => 6
[2] => 2
[total] => 19
)
[C] => Array
(
[0] => 9
[1] => 5
[2] => 1
[total] => 15
)
)
Aside from this option, you can also try brute-force and genetic algorithms, but bear in mind that they will be substantially slower. You'll have to decide if -34% in worst case scenario is a problem for you.
To follow up my original answer, the following code will generate all possible combinations of the boxes arranged in sets of 3 (brute-force approach):
class Combinations implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
//
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}
$fruits = array(1, 2, 4, 5, 6, 8, 9, 11, 14);
foreach(new Combinations($fruits, 3) as $k => $v)
echo implode(',', $v), "<br />\n";
The output:
1,2,4
1,2,5
1,2,6
1,2,8
1,2,9
1,2,11
1,2,14
1,4,5
1,4,6
1,4,8
1,4,9
1,4,11
1,4,14
1,5,6
1,5,8
1,5,9
1,5,11
1,5,14
1,6,8
1,6,9
1,6,11
1,6,14
1,8,9
1,8,11
1,8,14
1,9,11
1,9,14
1,11,14
2,4,5
2,4,6
2,4,8
2,4,9
2,4,11
2,4,14
2,5,6
2,5,8
2,5,9
2,5,11
2,5,14
2,6,8
2,6,9
2,6,11
2,6,14
2,8,9
2,8,11
2,8,14
2,9,11
2,9,14
2,11,14
4,5,6
4,5,8
4,5,9
4,5,11
4,5,14
4,6,8
4,6,9
4,6,11
4,6,14
4,8,9
4,8,11
4,8,14
4,9,11
4,9,14
4,11,14
5,6,8
5,6,9
5,6,11
5,6,14
5,8,9
5,8,11
5,8,14
5,9,11
5,9,14
5,11,14
6,8,9
6,8,11
6,8,14
6,9,11
6,9,14
6,11,14
8,9,11
8,9,14
8,11,14
9,11,14
Now you just need to select 3 distinct sets (the sum of each one should be 19, 20 and 21).
The solution on Delphi 2009 based on permutations (gives 14 4 2 9 5 6 1 8 11):
type
TIntegerArray = array of Integer;
procedure Permutation(K: Integer; var A: TIntegerArray);
var
I, J: Integer;
Tmp: Integer;
begin
for I:= 2 to Length(A) do begin
J:= K mod I;
Tmp:= A[J];
A[J]:= A[I - 1];
A[I - 1]:= Tmp;
K:= K div I;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
K, I: Integer;
A: TIntegerArray;
S: string;
BestWeight, BestIndex: Integer;
W1, W2: Integer;
begin
BestWeight:= 1000;
for K:= 0 to 2*3*4*5*6*7*8*9 - 1 do begin
A:= TIntegerArray.Create(1, 2, 4, 5, 6, 8, 9, 11, 14);
Permutation(K, A);
W1:= A[0] + A[1] + A[2];
W2:= A[3] + A[4] + A[5];
if W2 > W1 then W1:= W2;
W2:= A[6] + A[7] + A[8];
if W2 > W1 then W1:= W2;
if W1 < BestWeight then begin
BestWeight:= W1;
BestIndex:= K;
end;
end;
A:= TIntegerArray.Create(1, 2, 4, 5, 6, 8, 9, 11, 14);
Permutation(BestIndex, A);
S:= '';
for I:= 0 to Length(A) - 1 do
S:= S + Format('%3.d ', [A[I]]);
Edit1.Text:= S;
end;