使用笛卡尔算法进行 sku 组合
需求
对商品规格进行排列组合, 电商的 sku 商品组合
功能截图, 对商品规格进行组合排列
image
image
image
图中 16 和 9 是商品的分类 id, 分类 id 和商品 id 用竖杆分隔, 为了后续根据 id 去查抄回显使用. 有了这些组合的结果就可以做后续一些列操作.
核心代码, 使用笛卡尔乘积, 递归调用组合
- function doExchange(doubleArrays) {
- var len = doubleArrays.length;
- if (len>= 2) {
- var arr1 = doubleArrays[0];
- var arr2 = doubleArrays[1];
- var len1 = doubleArrays[0].length;
- var len2 = doubleArrays[1].length;
- var newlen = len1 * len2;
- var temp = new Array(newlen);
- var index = 0;
- for (var i = 0; i <len1; i++) {
- for (var j = 0; j < len2; j++) {
- temp[index] = arr1[i] + "," + arr2[j];
- index++;
- }
- }
- // 先把前两个数组进行组合
- var newArray = new Array(len - 1);
- newArray[0] = temp;
- if (len> 2) {
- var _count = 1;
- for (var i = 2; i <len; i++) {
- newArray[_count] = doubleArrays[i];
- _count++;
- }
- }
- // 创建新数组, 把前两项组合后数组作为新数组第一项, 从原数组第二项开始, 剩余未组合的值放进新数组, 递归调用新数组进行组合
- return this.doExchange(newArray);
- } else {
- return doubleArrays[0];
- // 长度小于 2 直接返回
- }
- }
快递员配送距离问题
需求
比如美团啊饿了么, 或者是电商类的平台, 需要配送餐饮和商品, 这时候快递员送餐员手里有多个订单, 这时候要告诉他应该以最优的路线进行配送
[图片上传失败...(image-ed52b-1559636263098)]
这是几个送餐点, 这个需求就是找出最优化路线.
核心代码
- /**
- * 定义一个最小堆对象
- */
- var heapMin = function () {
- this.set = [];
- }
- /**
- * 调整堆使其满足最小堆性质
- */
- heapMin.prototype.adjust = function (index) {
- let len = this.set.length
- let l = index * 2 + 1
- let r = index * 2 + 2
- let min = index
- let node = null
- if (l <= len -1 && this.set[min].cost> this.set[l].cost) {
- min = l
- }
- if (r <= len -1 && this.set[min].cost> this.set[r].cost) {
- min = r
- }
- if (min != index) {
- node = this.set[index];
- this.set[index] = this.set[min]
- this.set[min] = node
- this.adjust(min)
- }
- }
- /**
- * 插入一个元素
- */
- heapMin.prototype.push = function (node) {
- this.set.push(node)
- for (let i = Math.floor(this.set.length / 2); i>= 0; i--) {
- this.adjust(i)
- }
- }
- /**
- * 移除最小元素
- */
- heapMin.prototype.pop = function () {
- let node
- node = this.set.shift()
- this.adjust(0)
- return node
- }
- /**
- * 获取当前堆大小
- */
- heapMin.prototype.size = function () {
- return this.set.length
- }
- /**
- * 堆是否为空
- */
- heapMin.prototype.empty = function () {
- return this.set.length === 0 ? true : false
- }
- // 定义不可达路径值 -1
- const INF = -1
- // TSP 解空间树节点
- function TSPNode (cost, index) {
- // 节点解向量
- this.x = []
- // 当前走过的路径耗费值
- this.cost = cost
- // 当前节点在其解向量中的 index
- this.index = index
- }
- /**
- * TSP 对象
- * map: 地图, 采用邻接矩阵的方式表示无向图 G
- */
- function TSP (map) {
- // 检查地图数组合法性 n*n 数组
- if (map === undefined || !Array.isArray(map) || map.length <0 || !Array.isArray(map[0]) || map.length != map[0].length) {
- return console.error('map 非法!')
- }
- // 赋值地图数组
- this.map = map
- // 节点数量
- this.number = map.length
- // 当前最优路径耗费
- this.costBest = INF
- // 最优解向量数组
- this.xBest = []
- }
- /**
- * 计算最佳路径
- * 返回值: cost, 最佳路径耗费; routine, 路径
- */
- TSP.prototype.getBestRoutine = function () {
- // 暂存地图数组
- let map = this.map
- // 暂存节点数量
- let num = this.number
- // 创建一个最小堆
- let heap_min = new heapMin()
- // 创建初始节点, 因为从节点 0 出发, 所以 cost=0,index=1
- let startNode = new TSPNode(0, 1)
- // 初始化解向量, 数组中存储的是节点的序号, 对应 map 中的索引, 如:[0,1,...,n]
- for (let i = 0 ; i < num; i++) {
- startNode.x[i] = I
- }
- // 加入最小堆
- heap_min.push(startNode)
- // 开始搜索
- while (!heap_min.empty()) {
- // 取出当前节点
- var cNode = heap_min.pop()
- // 当前节点 id
- var cIndex = cNode.index
- // 搜索至倒数第二个节点时停止
- if (cIndex === num) {
- // 当前点可到达, 并且当前点可以到达初始点
- if (map[cIndex-2][cNode.x[cIndex-1]] != INF && map[cNode.x[cIndex-1]][0] != INF) {
- // 找到一个最优解, 进行记录
- if (this.costBest === INF || cNode.cost + map[cNode.x[cIndex-1]][0] < this.costBest) {
- this.costBest = cNode.cost + map[cNode.x[cIndex-1]][0]
- // 复制最优解向量
- for (let i=0; i < num; i++) {
- this.xBest[i] = cNode.x[I]
- }
- }
- continue
- }
- }
- // 判断当前节点是否满足限界条件, 如果不满足就不需要进行扩展
- if (this.costBest !== INF && cNode.cost>= this.costBest) {
- continue
- }
- // 没有到达叶子节点, 扩展子节点, 对于那些路径耗费大于当前最优路径耗费的子节点, 不需要扩展 (也称为剪掉), 即不加入最小堆中
- for(let j = cIndex; j <num; j++) {
- // 利用当前节点在其解向量中的索引获得上一个节点即 cIndex-1 的序号, 如果 x[cIndex-1] 节点与 x[j] 节点有边相连
- if (map[cNode.x[cIndex-1]][cNode.x[j]] != INF) {
- // 计算到达此节点的路径耗费
- let cost = cNode.cost + map[cNode.x[cIndex-1]][cNode.x[j]]
- // 对于那些路径耗费大于当前最优路径耗费的子节点, 不需要扩展 (也称为剪掉), 即不加入最小堆中. 当前路径耗费更小即 cost < this.costBest, 加入最小堆中
- if (this.costBest === INF || cost < this.costBest) {
- // 当前走过的路径耗费, 节点层数 + 1
- let node = new TSPNode(cost, cIndex +1)
- // 复制之前的解向量
- for (let i = 0; i < num; i++) {
- node.x[i] = cNode.x[I]
- }
- // 更新当前节点解向量
- let tmp = node.x[cIndex]
- node.x[cIndex] = node.x[j]
- node.x[j] = tmp
- // 加入最小堆中
- heap_min.push(node)
- }// end if
- }// end if
- }// end for 扩展子节点
- }// end while 搜索
- // 返回最优解向量
- return {
- cost: this.costBest,
- routine:this.xBest.join('-->')
- }
- }
- /**
- * map 地图数组
- * -1 : 表示不可达 INF
- **/
- var map = [
- [ -1, 8, 6,12,14,32],
- [ 8, -1, 8,30, 6,20],
- [ 6, 8, -1, 8, 5, 4],
- [12,30, 8, -1,20,12],
- [14, 6, 5,20, -1, 4],
- [32,20, 4,12, 4, -1],
- ]
- // 创建一个 TSP 对象
- var beginTime, endTime, res
- var tsp = new TSP(map)
- beginTime = new Date()
- res = tsp.getBestRoutine()
- endTime = new Date()
- console.log("cost:"+ res.cost +"\r\nroutine:" + res.routine+"\r\nexecute time:" + (endTime-beginTime) + "ms")
最短距离的参考链接
最少找零问题
需求
其实这个需求是我假想的, 因为现实中比如我在地铁站购买饮料, 很少投入大面额的一百去一瓶饮料, 基本上比较接近, 但是如果真的投入了一百, 这时候机器给我吐出来 90 个硬币我就崩溃了. 所以, 我更希望它以 50,20, 这样的最佳相加结果给我, 如果在这个机器已经有这个功能了, 那是我没用到, 如果没有我想应该加个, 不过现在大部分人使用扫码支付了.
核心代码 贪心算法
- function MinCoinChange(coins) {
- var coins = coins;
- this.makeChange = function (amount) {
- var change = [],total = 0;
- for(var i = coins.length; i>= 0; i--) {
- var coin = coins[i];
- while(total + coin <= amount) {
- change.push(coin);
- total += coin;
- }
- }
- return change;
- };
- }
- // 机器能够输出的钱币面额种类 [1,5,10,20,50,100]
- let typeMoney = [1,5,10,20,50,100]
- var minCoinChange = new MinCoinChange(typeMoney);
- // 投入的钱面额
- let maxMoney = 100
- console.log(minCoinChange.makeChange(maxMoney))
- // 代码核心思维就是从最大的开始拿, 并且对结果累加, 去和剩下的小面额的相加, 直到和 maxMoney 的数额相等为止.
程序本身还需要一些完善, 比如这段代码里还要对现有各种类型钱币个数做个实时统计, 所以钱币类型也是动态的, 如果没有 100 的就重新从 50 开始计算.
来源: http://www.jianshu.com/p/41c600053967