Ari*_*Ari 5 algorithm estimation traveling-salesman
什么是一个很好的启发式用于解决以下挑战？
Quality Blimps Inc.希望将销售额扩大到其他城市(N),因此他们聘请您作为推销员飞往其他城市销售飞艇.随身携带的Blimp价格昂贵,因此您需要确定每次旅行时携带多少飞艇以及何时返回总部以获得更多飞艇.Quality Blimps拥有无限量的飞艇.
您可以在您访问的每个城市只销售一个飞艇,但您不需要访问每个城市,因为有些城市的旅行费用很高.每个城市的初始价格都是飞利浦销售的,但随着更多的飞艇出售(并且新颖性消失),这个价格下降了一定比例.找到一条能够实现利润最大化的好路线.
https://www.hackerrank.com/codesprint4/challenges/tbsp
这个挑战类似于标准的旅行商问题,但有一些额外的曲折:推销员需要跟踪他自己的旅行费用和飞艇.每个城市都有不同的价格,而且这些价格在他的旅程中下降.什么是快速算法(即n log n)用于最大化利润？
以某种方式运输物品的价格使TSP更简单.如果推销员在A市并且想要去B,他可以比较直接到B的成本与首先返回总部以获得更多飞艇的成本.也就是说,通过A将额外的飞艇带到B或者回到中间是更便宜的.这项检查将创建一系列循环旅行,销售人员可以按照最高收入顺序进行.但是,首先确定这些循环的好方法是什么？