-2
$\begingroup$

With a group of 8 students you have set up a small business with which you help a customer every day during the holidays to clean up his computer and to redecorate it.

For the next day there are 12 possible customers. Everyone must got to one customer; so 4 customers can’t be helped that day.

For each combination, you know how much costs you have to incur to get a certain student to travel to a customer, this information is shown below in a table.

Of course you want to go to a layout where the total costs are minimal.

enter image description here

What is the minimum sum of the expenses if each student is going to help exactly one client, without students going to the same client?

$\endgroup$

closed as off-topic by Glorfindel, JonMark Perry, xhienne, PerpetualJ, Peregrine Rook Oct 16 '18 at 18:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Glorfindel, JonMark Perry, xhienne, PerpetualJ
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Is there a way to find the solution without trying all the possibilities? $\endgroup$ – xhienne Oct 16 '18 at 16:58
  • 2
    $\begingroup$ @xhienne There is! It's called the Hungarian Algorithm. Here's a great explanation that's directly applicable to this problem: youtube.com/watch?v=cQ5MsiGaDY8 $\endgroup$ – Blumer Oct 16 '18 at 17:04
  • $\begingroup$ Thanks a lot @Blumer. Can this be really considered as a puzzle then? This looks more like a mathematical problem or a computing problem. $\endgroup$ – xhienne Oct 16 '18 at 17:38
4
$\begingroup$

I did a highlighting strategy similar to what @gabbo1092 described. I highlighted the lowest cost for each row, starting at the top and moving down. When one of the columns already had a cost highlighted I would move on to the next lowest cost on that row. Next I compared the differences of the costs on the current row with the conflicting row in order to determine which column I should be switching.

(I think gabbo did not include this step, resulting in their selection of >!"S7->C9" + "S8->C10" = 50 + 44 = 94, rather than "S7->C12" + "S8->C9" = 51 + >!41 = 92).

Anyway here's my answer:
S1->C3: 43
S2->C8: 50
S3->C4: 41
S4->C5: 44
S5->C7: 41
S6->C6: 40
S7->C12: 51
S8->C9: 41

for a total of 351.

$\endgroup$
1
$\begingroup$

I didn't use a computer or algorithm to check (just used some logic) but I think this may be a possible solution:

S1->C3: 43
S2->C8: 50
S3->C4: 41
S4->C5: 44
S5->C7: 41
S6->C6: 40
S7->C9: 50
S8->C10: 44

this gives a total cost of 353. My method of solving was highlighting the lowest values in the rows and columns of the grid and attempting to optimize for the smallest possible numbers without using the same row or column twice.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.