Ask Question
15 April, 05:49

suppose that you are given two sets A and B, each containing positive integers. You can choose to reorder each set however you like. After reordering, letaibe theith element of set A, and letbibe theith element of set B. You then receive a payoff of∏ni=1abii. Givea polynomial-time algorithm that will maximize your payoff. Prove that your algorithm maximizes the payoff, and state its running time.

+4
Answers (1)
  1. 15 April, 07:42
    0
    We solve the problem with the following algorithms:

    1. Order A is in the increasing order.

    2. Order B is in the decreasing order.

    3. Return (A, B).

    Explanation:

    We need to show that this gives an optimal solution. without the loss of the generality, we can assume that a₁ ≤ a₂ ... ≤ aₙ in the optimal solution. Since the payoff is / prod_{i}^{n}=1^{a_{i}^{bi}}, the payoff will always increase if we make a change so that b_{i+1} > b_{i}. Therefore the optimal solution will be found if B is sorted.

    The running time is O (n log (n)) since we sort two vector.
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “suppose that you are given two sets A and B, each containing positive integers. You can choose to reorder each set however you like. After ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers