【仓库设置问题】

问题：

某公司在高速公路一些服务站内开设了百货超市，为了能及时给这些百货超市提供足够的商品，他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务，以满足各个超市对商品的需求。现已知这些百货超市在高速公路上的位置以及需要修建的仓库的数量。请编写程序确定每个仓库修建的位置以及所服务的超市，使所有仓库与所服务的百货超市的距离的总和最小，程序输出所求得的总的最小距离和。

要求仓库必须修在有超市的服务站内，不同的仓库必须修在不同的位置，不能修在同一服务站内，在同一服务站内的超市和仓库之间的距离可忽略不计。

输入描述：

输入的第一行有两个整数n和k,分别表示超市和仓库的数量，其中1 <= n <= 200, 1 <= k <= 30, k <= n。其后的n行，每一行有一个整数，表示每个超市的位置（相对于高速公路起点的距离）。

输出描述：

输出1行，一个整数，表示所有仓库与所服务的超市的距离的总和。

样例输入：

6 3

5

6

12

19

20

27

样例输出：

8

思路：

采用回溯法

解空间树是子集树。

我们可以在递归分支被目标函数截断后计算最小距离，如果距离小于最佳距离，更新。

代码：

#include<bits/stdc++.h>
using namespace std;int shops, wares;
int result = INT_MAX;int cal(int *shop, int *sign)
{int temp = 0;for(int i = 1; i <= shops; i++){if(!sign[i]){int a = i;int b = i;while(!sign[a] && a != 0) a--;while(!sign[b] && b != shops+1) b++;if(a == 0) temp += shop[b] - shop[i];else if(b == shops+1) temp += shop[i] - shop[a];else if((float)i < float(a+b)/2) temp += shop[i] - shop[a];else temp += shop[b] - shop[i];}}return temp;
}
void dfs(int *shop, int *sign, int cnt)
{if(cnt > wares){int dis = cal(shop, sign);if(dis < result) result = dis;return;}for(int i = 1; i <= shops; i++){if(sign[i]) continue;sign[i] = 1;dfs(shop, sign, cnt+1);sign[i] = 0;}
}
int main()
{cin >> shops >> wares;int *shop = new int[shops+2]();int *sign = new int[shops+2]();for(int i = 1; i <= shops; i++){cin >> shop[i];}sort(shop+1, shop+shops+1);dfs(shop, sign, 1);delete [] shop;delete [] sign;cout << result << endl;return 0;
}