当前位置: 首页 > news >正文

【仓库设置问题】

问题:

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

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

输入描述:

输入的第一行有两个整数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;
}

http://www.lryc.cn/news/361785.html

相关文章:

  • 深度学习知识与心得
  • Qt for Android
  • HTTP 的三次握手
  • 【Text2SQL 论文】T5-SR:使用 T5 生成中间表示来得到 SQL
  • 【HarmonyOS】应用屏蔽截屏和录屏
  • [BUG历险记] ERROR: [SIM 211-100] CSim failed with errors
  • Redis中大Key与热Key的解决方案
  • MySQL 视图(2)
  • Leecode---技巧---颜色分类、下一个排列、寻找重复数
  • ERC-7401:嵌套 NFT 标准的全新篇章
  • 代码随想录算法训练营Day6| 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和
  • 三十四、openlayers官网示例Dynamic clusters解析——动态的聚合图层
  • SpringBoot登录认证--衔接SpringBoot案例通关版
  • vue3状态管理,pinia的使用
  • 入门到实践,手把手教你用AI绘画!
  • 大模型应用框架-LangChain
  • 探索Linux中的强大文本处理工具——sed命令
  • 冯喜运:6.3黄金原油晚间最新行情及独家操作策略指导
  • Spark_SparkOnHive_海豚调度跑任务写入Hive表失败解决
  • SaaS 电商设计 (十一) 那些高并发电商系统的限流方案设计
  • 【算法】MT2 棋子翻转
  • 头颈肿瘤在PET/CT中的分割:HECKTOR挑战赛| 文献速递-深度学习肿瘤自动分割
  • Kafka重平衡导致无限循环消费问题
  • 执行shell脚本时为什么要写成./test.sh,而不是test.sh?
  • 【人工智能】第一部分:ChatGPT的基本概念和技术背景
  • 雪花算法详解及源码分析
  • Golang TCP网络编程
  • 先进制造aps专题十 aps项目成功指南
  • 实现Dropdown下拉菜单监听键盘上下键选中功能-React
  • Ubuntu系统升级k8s节点的node节点遇到的问题