How can i use greedy algorithm to allocate products to stores
I got assigned to solve this problem: Given number of products sold in specific stores, is there a way to find from which stores to buy all products with the condition of buying only one product from each store.
For example if you have stores A,B,C and products a,b,c with each shop selling:
A: a,c
B: a,b,c
C: c
Answer: You will be buying products a from store A product b from store B and product c from store C.
From this am assuming you cant have more products than stores since you are buying just 1 product from each store and you want to buy all of them.
My thought was using a greedy algorithm where you first buy products exclusively sold in one store and solving this hierarchically but it doesn't always work
You could solve it by finding the max-flow on a maximum cardinality matching in a bipartite graph. Construct a source s going to all the stores, {A, B, C}, and draw a directed edge to each product that store has, {a, b, c}. Then the products to the sink, t. Label all edges with 0/1.
Then apply the greedy Ford–Fulkerson method. If the max-flow reaches the number of stores and the number of products, then one has a viable solution. This will complete in at most O((number of stores, products)✖️(number of edges)), since the maximum capacity is the number of stores and products, and each iteration increases the capacity.
- Mathematical explanation of Leetcode question: Container With Most Water
- How to check a point is inside an ellipsoid with orientation?
- algorithm to trace border in 2D array
- Red Black Tree Black Height Increase after Insertion
- Coin Change II : To take a value or not to
- Logic to implement to get maximum points
- Generate all strings under length N in C
- Algorithm to extract overlapping range
- Merging two sorted linked lists
- Median of two sorted-arrays algorithm for O(log(m+n))
- Calculating new longitude, latitude from old + n meters
- Calculation of Average Queue Length in a Simple Queueing Model
- what is the most efficient way to gather all points at a certain height?
- Does a recursive segment tree require more space than an iterative one?
- Tarjan Algorithms for SCC
- Is there a balanced BST with each node maintain the subtree size?
- Sort on a string that may contain a number
- Optimally counting number of nodes in a complete binary tree
- Fraction to Recurring Decimal
- Quicksort with Python
- What is the optimal algorithm for the game 2048?
- Asteroid Mining - Dynamic Programming problem
- Optimize performance for dense ranking algo
- Looking for a sort algorithm with as few as possible compare operations
- How to remove a line by its number from file without rewriting file python
- The output gives the same result
- Radix sort slower than expected compared to standard sort
- How to find minimum pairing cost? (Any Language)
- Algorithm to minimize the number of printing plates when printing sheets of stickers
- Travel from city 1 to city n, visiting at least 3 odd cities