Minimum number of shoes

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
New poster
Posts: 1
Joined: Sun Mar 17, 2013 1:12 pm

Minimum number of shoes

Post by chalao » Sun Mar 17, 2013 1:17 pm

Hello. There is this problem I can't solve. Would you provide me some ideas to solve it?

There are two boxes.Each contains shoes of different colors. Given the number of shoes for each color for each of the two boxes, determine the minimum number of shoes that should be taken from each box to guarantee that we will have at least a pair of shoes of the same color (of course yo can't look into the box while taking the shoes out).

The goal is to minimize the total number of shoes taken. The problem should be solved in one second, with 20 different colors at most, and 128 shoes of each color at most. In case of multiple solutions one should take the one in which less shoes from box #1 are taken

For example: In box #1 there are 0 red shoes, 7 blue shoes, 1 yellow shoe, and 6 white shoes.
In box #2 there are 1 red shoe, 5 blue shoe, 0 yellow shoes, and 6 white shoes.

The minimum number of shoes that need to be taken from box #1 is 2 and from box #2 is 8.


Post Reply

Return to “Algorithms”