【动态规划】将一个包含m个整数的数组分成n个数组，每个数组的和尽量接近

// 将数组分成n个数组，每个数组的和尽量接近
func GetAvgArr(numberList []int64, arrNum int) [][]int64 {
	avgArrays := make([][]int64, 0)
	if len(numberList) == 0 || len(numberList) < arrNum {
		return avgArrays
	}

	// 1. 计算平均值
	var sum, mean float64
	numberListFloat64 := make([]float64, 0)
	for _, num := range numberList {
		numberListFloat64 = append(numberListFloat64, float64(num))
		sum += float64(num)
	}
	mean = sum / float64(arrNum)

	// 2. 倒序排序
	sort.Sort(sort.Reverse(sort.Float64Slice(numberListFloat64)))

	for cnt := 0; cnt < arrNum; cnt++ {
		//fmt.Println("mean = ", mean)
		var arr []float64
		if cnt == arrNum-1 {
			// 最后一组，返回数组剩余所有数
			avgArrays = append(avgArrays, transFloatToIntList(numberListFloat64))
			break
		}
		// 如果最大的数max>=mean，这个数单独一个组
		if len(numberListFloat64) > 0 && numberListFloat64[0] >= mean {
			arr = []float64{float64(numberListFloat64[0])}
			avgArrays = append(avgArrays, transFloatToIntList(arr))
			sum = sum - numberListFloat64[0]

			// 重新计算剩下partition的平均值
			mean = sum / float64(arrNum-len(avgArrays))
		} else {
			// 否则寻找一组数据
			arr, _ = getList(numberListFloat64, mean, math.Pow(mean, 2))
			avgArrays = append(avgArrays, transFloatToIntList(arr))
		}
		// 将已经形成一组的数据从原数组中移除，准备寻找下一组数据
		numberListFloat64 = removeFromFloatList(numberListFloat64, arr)
	}

	return avgArrays
}

// 将[]float64转为[]int64
func transFloatToIntList(floatList []float64) []int64 {
	res := make([]int64, 0)
	for _, item := range floatList {
		res = append(res, int64(item))
	}
	return res
}

// 将在removeNums中出现过的数字从originalList中移除
func removeFromFloatList(originalList []float64, removeNums []float64) []float64 {
	res := make([]float64, 0)
	from := 0
	for _, remove := range removeNums {
		for i := from; i < len(originalList); i++ {
			if originalList[i] == remove {
				res = append(res, originalList[from:i]...)
				from = i + 1
				break
			}
		}
	}
	res = append(res, originalList[from:]...)
	return res
}

func getList(arr []float64, delta, distance float64) ([]float64, float64) {
	res := make([]float64, 0)
	if len(arr) == 0 {
		return res, -1
	}

	for i := 0; i < len(arr)-1; i++ {
		switch true {
		case delta == arr[i]:
			res = append(res, arr[i])
			return res, 0
		case delta < arr[i]:
			continue
		case delta > arr[i]:
			if i == 0 {
				res = append(res, arr[i])
				delta = delta - arr[i]
				distance = math.Pow(delta, 2)
				tmp, d := getList(arr[i+1:], delta, distance)
				res = append(res, tmp...)
				return res, d
			} else {
				dis1 := math.Pow(arr[i-1]-delta, 2)
				dis2 := math.Pow(delta-arr[i], 2)
				if dis1 > dis2 {
					res = append(res, arr[i])
					delta = delta - arr[i]
					tmp, d := getList(arr[i+1:], delta, dis2)
					res = append(res, tmp...)
					return res, d
				} else {
					tmp, d := getList(arr[i:], delta, dis2)
					if dis1 > d {
						res = append(res, tmp...)
						return res, d
					}

					res = append(res, arr[i-1])
					return res, dis1
				}
			}
		}
	}

	dis := math.Pow(delta-arr[len(arr)-1], 2)

	if dis < distance {
		return arr[len(arr)-1:], dis
	}

	return make([]float64, 0), -1
}

func main() {
	partitionList := []int64{500, 18, 28, 2, 27, 35, 22, 10, 6, 5, 3, 2, 1}
	fmt.Println("test partitionList is : ", partitionList)
	fmt.Println("result is :")
	arrays := stage.GetAvgArr(partitionList, 4)
	for i, arr := range arrays {
		fmt.Printf("arr %d is : %d, ", i, arr)
		var sumValue int64
		for _, value := range arr {
			sumValue += value
		}
		fmt.Println("sum = ", sumValue)
	}
}