Question

In 2006,the city of Beijing,China,instituted a policy that limits residents to own at most one dog per household. Imagine you are running an online pet adoption website for the city. Your website contains pictures of adorable puppies that are available for adoption, and it allows for dogless Beijing residents to click on as many puppies as they like, with the understanding that they can adopt at most one. Suppose now that you have collected the puppy preferences from among n Beijing residents for your m puppies. Describe an efficient algorithm for assigning puppies to residents that provides for the maximum number of puppy adoptions possible while satisfying the constraints that each resident will only adopt a puppy that he or she likes and that no resident can adopt more than one puppy. Show flow network.

Answer 1

Following are the responses to the given question:

Step-by-step explanation:

Let P become the number of puppies just on the portal who've already received at least one like.

Similarly, the number of households with no household pet and those who are in search of a puppy is R.

We'll have a chart of citizens who liked a puppy p in P now. As a consequence, we will be having -

`p_1 = r_1(number_{puppy_(liked)}),\ r_2(number_{puppy_(liked)}) ..`

So p1 is a puppy that r1 and r2 want. (number puppy liked) was its amount of puppies that r1 has enjoyed.

Algorithm

1. Sort the puppies (p1,p2,..) from set P in an attempt about how many likes those who got from the citizens.
2. If a puppy
   `P_n` only receives one like, give it over to the resident who's closest to it. Remove the puppy from the registry of residents too though.
3. After tenants have indeed been withdrawn, sort the collection once more and repeat steps 2.
4. When there isn't a puppy left for a single citizen, assign one to the resident with both the fewest like. For example, if p = r1(2), r2(4), Assign puppy p to r1 in this situation, as it only has two likes remaining. Delete r1 from the puppy's bookmarks folder then repeat phase 3 as r1 has been deleted again.
5. Reply steps 3 and 4 until the number of puppies left is zero or the tenant's total is zero.