Good day. Subset sum selection problem is NP-hard.
I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of size K, so that sum of all selected items and items within radius(when selected items is in center) is maximal.
Here example(with radius 1 and K=2):
On this picture 2 orange items selected. all blue and green items are added to sum also, but green item, added only once( in other words any item on grid can be taken once in final sum).
So sum of selected subse: 2xOrange(selected)+9xBlue(adjacent)+1xGreen(taken only once into account).
When radius is 0 the problem is trivial: Just choose K best items, But when radius 1 or more is following problem NP-hard?
If yes, what is the best way to prove it ?
If no, is there an algorithm that return optimal solution?
Many thanks for help!