Question

A group of friends (n of them) from the town of Nocillis visit the vineyards of Apan to taste wines. The vineyards produce many fine wines (m different varieties) and the friends decide to buy 3 bottles of wine each if they are available to purchase. Unfortunately, the vineyards of Apan have a peculiar restriction that they cannot sell more than one bottle of the same wine. So, the vineyards come up with the following scheme: They ask each person to write down a list of up to 10 wines that they enjoyed and would be happy buying. With this information, give an O(m + n 3/2 ) time algorithm to help the vineyards maximize the number of wines that they can sell to the group of friends. Less efficient solutions will receive less credit.

Answer 1

Check the explanation

Step-by-step explanation:

We can solve this question by Ford-Fulkerson algorithm where the maximum flow is the number of maximum wines sold by the vineyard.

The Ford-Fulkerson algorithm is a greedy algorithm that is used to find maximum flow in a flow network.

Ford-Fulkerson Algorithm:

1. Initial Flow = 0, maximum_flow = 0, and start from the Source

2. Find each path from Source to Sink using BFS/DFS while reducing capacity of each edge by amount of flow and add flow to maximum_flow

3. return maximum_flow

Running Time-Complexity: O(maximum_flow*|E|) where |E| = no. of edges

For this problem, we will take n + m + 2 (A source vertex and a Sink vertex) vertices.

and, there will be following edges,

m edges as (S, Wi) where i-1,2...m and weight-capacity = 1 each

m*n edges as (Wi, Fj) where i=1,2...m, j=1...n and weight-capacity = 1 each

n edges as (Fj, T) where j=1,2...n and weight-capacity = 3 each

Here,

n vertices edges(each represents a friend) will have weight capacity as 3, thus ensuring that no friend can get more than 3 wines.

m vertices edges(each represents a wine) will have weight capacity as 1, thus ensuring that each wine can be sold one time at most.

Time-Complexity (Worst time):

Total Edges = m+n+10n = m+11n

maximum_flow possible = 3n (n friends can buy max 3 wines max)

= O((m+11n)*3n)

= O(mn+n^2)