做h5那个网站好,深圳大型商城网站建设,美心西饼在哪个网站做问卷调查,什么网站是vue做的问题#xff1a;
某公司在高速公路一些服务站内开设了百货超市#xff0c;为了能及时给这些百货超市提供足够的商品#xff0c;他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务#xff0c;以满足各个超市对商品的需求。现已知这些百货超市在高…问题
某公司在高速公路一些服务站内开设了百货超市为了能及时给这些百货超市提供足够的商品他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务以满足各个超市对商品的需求。现已知这些百货超市在高速公路上的位置以及需要修建的仓库的数量。请编写程序确定每个仓库修建的位置以及所服务的超市使所有仓库与所服务的百货超市的距离的总和最小程序输出所求得的总的最小距离和。
要求仓库必须修在有超市的服务站内不同的仓库必须修在不同的位置不能修在同一服务站内在同一服务站内的超市和仓库之间的距离可忽略不计。
输入描述
输入的第一行有两个整数n和k,分别表示超市和仓库的数量其中1 n 200, 1 k 30, k n。其后的n行每一行有一个整数表示每个超市的位置相对于高速公路起点的距离。
输出描述
输出1行一个整数表示所有仓库与所服务的超市的距离的总和。
样例输入
6 3
5
6
12
19
20
27
样例输出
8 思路
采用回溯法
解空间树是子集树。
我们可以在递归分支被目标函数截断后计算最小距离如果距离小于最佳距离更新。 代码
#includebits/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 ! shops1) b;if(a 0) temp shop[b] - shop[i];else if(b shops1) temp shop[i] - shop[a];else if((float)i float(ab)/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, cnt1);sign[i] 0;}
}
int main()
{cin shops wares;int *shop new int[shops2]();int *sign new int[shops2]();for(int i 1; i shops; i){cin shop[i];}sort(shop1, shopshops1);dfs(shop, sign, 1);delete [] shop;delete [] sign;cout result endl;return 0;
}
