IT教程 ·

Golang完成高性能凑单东西:给定<金额列表>盘算<目的金额>一切组合

代码演示C#各版本新功能

 

一、需求

公司有一个比较坑爹的报销计划,须要依据一堆细碎的发票中,凑出一个目的金额,请求偏差在1块钱之内。
比方:你有一堆发票[100, 101, 103, 105, 106, 132, 129, 292, 182, 188, 224.3, 40.5, 35.9, 32.5, 39, 12, 17.5, 28, 35, 34, 26.32, 28, 35, 39, 25, 1, 24, 35, 45, 47, 32.11, 45, 32, 38.88, 44, 36.5, 35.8, 45, 26.5, 33, 25, 364, 27.3, 39.2, 180, 279, 282, 281, 285, 275, 277, 278, 200, 201, 1959.12, 929.53, 1037.03, 1033.9],让你从这堆票中凑出5000块来,然后最多不能超过1块钱。你瞧瞧这是人干的事么!

瑕玷:每次人肉去对照,糟蹋大批的时刻。
操作历程也许是如许的:新建一个excel表格,将一切的金额录入,然后本身勾选发票,直到目的金额涌现,以下图
Golang完成高性能凑单东西:给定<金额列表>盘算<目的金额>一切组合 IT教程 第1张
品德大迸发的时刻一下就凑出来,命运运限不好的时刻凑着凑着一两个小时就过去了!
因而,我们急需一个程序本身去干这个事。

二、完成思绪

  1. 最差计划:全组合
    运用全组合,搜刮一切组合计划,遍历满足的效果输出,时刻复杂度为O(n!),本来挪用了python的排列组合函数完成,效果卡得不行,有时刻能把程序跑挂了
  2. 中等计划:回溯暴力破解
    应用回溯输出,存在反复递归,时刻复杂度为O(2^n),平常来讲已满足平常需求,然则假如n很大,照样影响机能
  3. 最优计划:动态计划
    时刻复杂度为O(n*w),为最快计划,提拔气质指数,5颗星!

三、终究计划:动态计划

终究用动态计划头脑完成,空间换时刻,200个碎票婚配1万的金额秒出效果,也许运用800M内存,

代码已贴到github:

中心代码以下

package main

import (
    "fmt"
    "github.com/shopspring/decimal"
    "strconv"
)

type AmountCalculator struct {
    maxValue int   //期望值(单位为分)
    items    []int //发票金额(单位为分)
    overflow int   //许可的偏差值(单位为分)
}

//items:一切发票 maxValue:目的金额 overflow:许可偏差金额
func New(items []float64, maxValue float64, overflow float64) *AmountCalculator {
    obj := &AmountCalculator{}
    obj.maxValue = obj.dollarToCent(maxValue)
    obj.overflow = obj.dollarToCent(overflow)
    centItems := make([]int, len(items))
    for i, v := range items {
        centItems[i] = obj.dollarToCent(v)
    }
    obj.items = centItems
    return obj
}

//元转分
func (this *AmountCalculator) dollarToCent(value float64) int {
    value, _ = strconv.ParseFloat(fmt.Sprintf("%.2f", value), 64)

    decimalValue := decimal.NewFromFloat(value)
    decimalValue = decimalValue.Mul(decimal.NewFromInt(100))

    res, _ := decimalValue.Float64()
    return int(res)
}

//分转元
func (this *AmountCalculator) centToDollar(v int) float64 {
    value := float64(v)
    value, _ = strconv.ParseFloat(fmt.Sprintf("%.2f", value/100), 64)
    return value
}

//实行盘算,返回一切计划
func (this *AmountCalculator) GetCombinations() [][]float64 {
    items := this.items
    n := len(this.items)
    max := this.maxValue + this.overflow
    states := this.createStates(len(this.items), max+1)

    states[0][0] = true
    if items[0] <= max {
        states[0][items[0]] = true
    }

    for i := 1; i < n; i++ {
        //不选
        for j := 0; j <= max; j++ {
            if states[i-1][j] {
                states[i][j] = states[i-1][j]
            }
        }
        //选中
        for j := 0; j <= max-items[i]; j++ {
            if states[i-1][j] {
                states[i][j+items[i]] = true
            }
        }
    }
    //猎取终究一切满足的计划
    res := make([][]float64, 0)
    for j := this.maxValue; j <= max; j++ {
        for i := 0; i < n; i++ {
            if states[i][j] {
                //推断必需末了一个选中才算,要不区间有重合 比如前5个元素已满足目的金额了,state[5][w]=true,然后state[6][w]也是true,存在反复的计划
                if i == 0 {
                    //第一个元素已满足
                    res = append(res, this.getSelected(states, items, i, j))
                } else if j-items[i] >= 0 && states[i-1][j-items[i]] == true {
                    res = append(res, this.getSelected(states, items, i, j))
                }
            }
        }
    }
    return res
}

//猎取一切选中的元素(倒推)
func (this *AmountCalculator) getSelected(states [][]bool, items []int, n, max int) []float64 {
    var selected = make([]int, 0)
    for i := n; i >= 1; i-- {
        //元素被选中
        if max-items[i] >= 0 && states[i-1][max-items[i]] == true {
            selected = append([]int{items[i]}, selected...)
            max = max - items[i]
        } else {
            //没选,max分量稳定,直接进入下一次
        }
    }

    //假如max不为0,申明还须要追加第一个元素
    if max != 0 {
        selected = append([]int{items[0]}, selected...)
    }

    dollarItems := make([]float64, len(selected))
    for i, v := range selected {
        dollarItems[i] = this.centToDollar(v)
    }
    return dollarItems
}

//初始化一切状况
func (this *AmountCalculator) createStates(n, max int) [][]bool {
    states := make([][]bool, n)
    for i, _ := range states {
        states[i] = make([]bool, max)
    }
    return states
}

四、运用体式格局

1.直接挪用代码(合适用来开发本身的软件)

package main

import (
    "fmt"
    "github.com/chenqionghe/amount-calculator"
    "time"
)

func main() {
    //一切碎票
    items := []float64{100, 101, 103, 105, 106, 132, 129, 292, 182, 188, 224.3, 40.5, 35.9, 32.5, 39, 12, 17.5, 28, 35, 34, 26.32, 28, 35, 39, 25, 1, 24, 35, 45, 47, 32.11, 45, 32, 38.88, 44, 36.5, 35.8, 45, 26.5, 33, 25, 364, 27.3, 39.2, 180, 279, 282, 281, 285, 275, 277, 278, 200, 201, 1959.12, 929.53, 1037.03, 1033.9}
    //目的金额
    target := float64(5000)
    //许可超越
    overflow := float64(1)
    obj := amountcalculator.New(items, target, overflow)

    startTime := time.Now()

    //猎取一切的组合
    res := obj.GetCombinations()
    for _, v := range res {
        fmt.Println(v)
    }
    fmt.Printf("total:%d used time:%sn", len(res), time.Now().Sub(startTime))
}

运转效果

[100 101 103 105 106 132 129 292 182 188 224.3 40.5 12 17.5 35 34 26.32 28 35 39 25 1 24 35 45 47 45 32 38.88 44 36.5 45 26.5 33 25 364 27.3 39.2 180 279 282 281 285 275 277 278]
[100 101 103 105 132 129 292 182 188 35.9 39 12 17.5 28 35 34 26.32 28 35 39 25 1 24 35 45 47 32.11 45 32 38.88 44 36.5 35.79 45 26.5 33 25 364 27.3 39.2 180 279 282 281 285 275 277 278 200]
...
[35.9 25 24 38.88 36.5 35.79 45 26.5 33 25 27.3 39.2 180 279 282 281 285 275 277 278 200 201 1037.03 1033.9]
total:577 used time:97.048224ms

耗时97毫秒,共盘算出577种计划,机能高到使人不由得想拍手!

这类体式格局合适在本身开发的程序中运用,比如要出一个web界面,给前端供应数据

2.命令行形式(合适不会编程的人运用)

这类体式格局合适不会go言语,或许不会编程的人运用,只需编译出对应平台的版本就行。
一次编译屡次分发,相称于copy了个绿色版软件到电脑上直接运用

编译历程以下

  • 新建一个go文件:main.go
package main

import (
    "github.com/chenqionghe/amount-calculator"
)

func main() {
    amountcalculator.RunCliMode()
}
  • 编译
go build -o amount-calculator
  • 运转该东西
 ./amount-calculator -max=156 -overflow=1 -items=12,135,11,12,15,16,18,32,64,76,50
156 [11 15 16 18 32 64]
156 [16 64 76]
156 [12 18 76 50]
157 [12 15 16 18 32 64]
157 [15 16 18 32 76]
157 [15 16 76 50]

能够看到,命令行直接输出了一切婚配的组合,还给出了每一个组合的金额,关于运用者来讲,不会编程言语也完整没有关系,只须要本身实行一下即可,相称轻易。

别的,命令行形式省了一个编译的历程,效力更高,引荐!

五、总结

手艺解放生产力,这类反复且费时的劳动完整应该由程序去做,惋惜的是

  1. 平常的产物提不出如许的需求
  2. 产物纵然能提如许的需求,开发也不一定能完成出来
  3. 开发纵然能完成出来,程序也不一定能跑得动,由于极可能太耗内存或太耗CPU,还没等效果运转出来程序就挂了

哈哈,轻微有点吹嘘逼了,不论怎样,就一句话:yeah buddy! light weight baby! 让我听到你们的尖叫声!

使用C#开发pdf阅读器初探(基于WPF,没有使用开源库)

参与评论