# How to the NP hard of a problem that search for a subset of points with maximum scores?

Suppose in a plane, there is a set of points, whose distance to $$(0,0)$$ is always 1:

$$[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$$

Each point is assigned with a weight (possible negative):

$$[w(0,1) = 1, w(1,0) = 2,w(0.707,0.707) = -1,w(0.707,-0.707)= -2,...]$$

Suppose the standard deviation of the points are defined as the top answer here: https://stats.stackexchange.com/questions/13272/2d-analog-of-standard-deviation

Find a subset of points $$S$$ such that SUM(w)×STD is maximized.

My gut feeling is that this problem is NP hard. Very similar to knapsack problem. However, knapsack use weight as a threshold. I'm not sure how to transfer the standard deviation here. Any thought on how to prove this would be appreciated!

• Depends on what u mean by STD here? all points have distance 1 from (0,0) so they r on a circle of raduis 1. It seems u should calculate the STD according to the weight values compared to the expected weight of all points, is that what u mean??? – ShAr May 11 '20 at 20:36
• Hi ShAr, STD is defined in the link above. STD and weight are two independent factors, which we want to find a set of points whose product of two factors are maximized. Yes, points are on a circle of radius 1. The intuition behind is that, we want to find a set of points with maximum weight, and at the same time hope they are dispersed in the plane. – Zachary HUANG May 12 '20 at 21:54