Edit: My other answer is better than this one; look at that one instead.
The problem can be represented by making a grid filled with dots. The grid has:
- N rows, one for each person.
- M columns, one for each item.
- One green dot whenever a person is willing to give an item (because "give" starts with "G" for "green"). For example, if Bob is willing to trade up to three apples, then put 3 green dots in the grid cell which is in the row representing Bob and the column representing apples.
- One red dot whenever a person wants to receive an item.
(In mathematical terms, this would be two N × M matrices, called G and R.)
Here's one algorithm for solving your problem. It's probably not the best algorithm, but it's an algorithm.
First, transform the grid into a directed graph by taking these two steps:
- Draw an arrow from every green dot to every red dot in the same column (indicating that one person can give an item and another person can receive it).
- Draw an arrow from every red dot to every green dot in the same row (indicating that a person can receive one item and give another item).
Second, find a directed cycle in the graph. This cycle provides the answer.
As an example, suppose that Bob has an apple and wants an orange, and Sarah has an orange and wants an apple. The grid would contain
- a green dot for (Bob, apple),
- a green dot for (Sarah, orange),
- a red dot for (Bob, orange), and
- a red dot for (Sarah, apple).
The cycle that we find
- starts at the green dot (Bob, apple) and goes to the red dot (Sarah, apple) (Bob gives an apple and Sarah receives it);
- goes from the red dot (Sarah, apple) to the green dot (Sarah, orange) (since Sarah received an apple, she's willing to give an orange);
- goes from the green dot (Sarah, orange) to the red dot (Bob, orange) (Sarah gives an orange to Bob); and
- returns from the red dot (Bob, orange) back to the green dot (Bob, apple) (Bob received an orange and so he's willing to give up an apple).