CODEWITHSUNDEEP
algorithmdynamic-programmingnp
Abhishek
Abhishek

Reputation: 29

Is this NP-Complete?

So I have N Apples located at Points in a 2-D Coordinate Plane, and a point P.

I also have X Carts , each with max capacity Y. I want to take all the apples to the point P . I need to find an arrangement(Which apples to pick with each cart) such as to minimize the total distance each cart has to travel.

  1. There is no starting point, you can start the cart at any of the N points.
  2. Each cart can carry any number of apples <= Y.

Is there a solution better than brute-force for this problem, O(N^Y)

Upvotes: 1

Views: 64

Answers (1)

Codor
Codor

Reputation: 17605

The described problem is NP-complete as it is a generalization of the Euklidean Travelling Salesman Problem; it contains the special case where there is X=1 cart with capacity N. The problem stated in the question is termed a Vehicle Routing Problem, as multiple carts are involved.

Upvotes: 2

Related Questions