给定固定长度绳索 求二维平面可包围最大石头数量的算法求解

这是一道算法编程题：

二维平面上分布有若干石头，给定一段已知长度的绳索，求使用这段闭合绳索最多可以包围多少个石头？（绳索必须为闭合状态）

我最初认为这道题等价于在无向图中寻找长度不超过上限、包含节点数最多的环，BFS似乎是可行解法，但这个问题看起来属于NP-hard问题。

补充说明 #

举个例子：平面上共有5个石头，共有三种包围方案：黑色、红色、蓝色。每种方案的绳索长度是所有边的长度之和。
该问题等价于：从N个点中按顺序选出$x_1,...x_n$共n个点，满足总长度和 = $d(x_1,x_2)+d(x_2,x_3)+...+d(x_{n-1},x_n)+d(x_n,x_1) ≤ C$，其中n>1，求n的最大值。

参考解法 #

经过提示后，我发现该问题和无向图无关，它和从给定数组中选出若干元素和等于目标值的问题类似，但区别在于本题的结果和选择顺序相关，因此不能按照数组原有顺序选择。以下是我的解法，但仍存在大量重复搜索的问题，比如如果某符合条件的环有4个节点，我们会从4个节点分别出发重复搜索4次。

// 计算两点之间的欧氏距离
double d(const vector<double> a, const vector<double> b)
{
    return sqrt((a[0] - b[0])*(a[0] - b[0]) + (a[1] - b[1])*(a[1] - b[1]));
}

/*
递归搜索函数
参数说明：
array: 存储所有石头坐标的数组
target: 剩余可用的绳索长度
out: 当前已经选入路径的点
sum: 当前路径的总长度
ct: 目前搜索到的最大可包围石头数量
res: 用于调试时存储合法路径结果
visited: 标记已经被选入路径的点，避免重复选择
*/
void help(vector<vector<double>> array, double target, vector<vector<double>> &out, int &sum, int & ct, vector<vector<vector<double>>> &res, vector<bool> &visited)
{
    // 由于选择顺序会影响结果，需要从头遍历所有点，用visited跳过已选的点
    for (int i = 0; i < array.size(); i++) 
    {
        if (visited[i]) continue;
        else if (out.empty()) {
            out.push_back(array[i]); 
            visited[i] = true;
        }
        else
        {
            vector<double> last = out.back(), first = out.front();
            // 判断加入当前点后，闭合路径的总长度是否不超过绳索上限
            if (sum + d(array[i], last) + d(array[i], first) <= target)
            {
                out.push_back(array[i]);
                sum += d(array[i], last);
                ct = max(ct, (int)out.size());
                visited[i] = true;
                // 递归搜索下一个点，传入剩余可用长度
                help(array, target - d(array[i], last), out, sum, ct, res, visited);
                // 回溯，恢复上一层的状态
                out.pop_back();
                sum -= d(array[i], last);
                visited[i] = false;
            }
            else
            {
                res.push_back(out);
                return;
            }
        }
    }
}
int Path(vector<vector<double>> array, double target) {
    int sum = 0, ct = 0; 
    vector<vector<double>> out;
    vector<vector<vector<double>>> res;
    vector<bool> visited(array.size(), false);
    help(array, target, out, sum, ct, res, visited);

    return ct;
}

内容的提问来源于stack exchange，提问作者user6703592