I ran into an algorithmic problem, but I can’t understand anything better than brute force or reduce it to a more famous problem. Any hints?
There are N bags with variable sizes and N types of items. Each type of item belongs to one bag. There are many items of each type, and each item may have a different size. Initially, these items are distributed randomly across all bags. We must place the items in appropriate bags. However, we can only work with a pair of bags at a time, exchanging elements (as much as possible) and move on to the next pair. The goal is to reduce the total number of pairs. Edit: the goal is to find a gear sequence that minimizes the total number of bag pairs involved
Clarification :
The bags are not arbitrarily large (you can assume that the size of the bag and items should be an integer from 0 to 1000, if that helps). You often come across scenarios in which all items between two bags cannot be replaced due to the limited capacity of one of the bags. Here the algorithm should do the optimization. Perhaps if another pair of bags were replaced first, the current exchange can be done at a time. To illustrate this, consider Bags A, B, and C and their items 1, 2, 3, respectively. The number in parentheses is the size.
A (10): 3 (8)
B (10): 1 (2), 1 (3)
C (10): 1 (4)
Swap orders can be AB, AC, AB or AC, AB. The latter is optimal, since the number of swaps is less.
source
share