2
$\begingroup$

There are m people and n kinds of objects. Each person has exactly one instance of each kind of objects, but these objects have different values associated. Now I want to find a subset of objects from all those m*n objects satisfying the condition: it should have p objects of each kind (p < m), and a person cannot contribute more than p objects. I want to maximize the total value of the objects picked. I have tried several obvious greedy algorithms, but none of them has found the optimal solution. Is there an algorithm that is not NP hard?

$\endgroup$
1
$\begingroup$

Yes sure. You can solve this problem using Minimum Cost Maximum Flow technique. With this algorithm you can find the maximum flow in a network with weighted edges that have minimum total weight (weights can be negative). So let's build the model that fits our problem best.

Build the following graph

enter image description here

  • There are $n$ nodes in the set $A$ that represent each person.
  • There are $m$ nodes in the set $B$ that represent each type of object.

The set $A$ and $B$ are full connected the edge $e_{i,j}$ that connects node $A_i$ and $B_j$ has:

  • capacity: 1 (It can be taken at most once)
  • cost: $-w_{i,j}$ (We are looking maximum which is the same as minimize the negation of each value)

Source node $S$ is connected with an edge to each node in the set $A$.

  • capacity: $p$ (each person can carry at most $p$ objects)
  • cost: 0

Nodes on set $B$ are connected to target node $T$.

  • capacity: $p$ (each object can be carried by at most $p$ persons)
  • cost: 0

Maximum flow in this graph is $m * p$ since there is an answer where each object is taken exactly $p$ times. Minimum cost is the negation of the answer you are looking for.

This problem is in P.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.