资源均分

资源均分

背景

  这道题目说实话我目前还不知道最优或者标准的做法是什么，它不像是一些标准的dp、树啊之类的问题。

题目

  假设在中东各个国家都有一定的石油库存，每个国家的库存可能不一样，现在你作为掌管石油的老大，你手中有M吨石油，如何分配石油给这些国家，让整体的石油分布看上去比较均衡，你可以分配手中的M吨石油，但是不能在各个国家之间调拨石油。你分配的越好，越不会引起战争。

  这里有两点需要注意，

1、整体的分布比较均衡，并没有说具体的衡量标准是什么，如何定义均衡需要自己思考。

2、各个国家之间的石油不能相互调拨，你只能分配手中的M吨石油。

  这里的看上去均衡，并不是一定要求大家的石油都一样，而是让国家之间的石油分布差异不是很大，若能完全均衡当然是最好。

我的第一个思路是找到最大的那个国家的石油n，然后计算其它国家与的石油与n的差值，然后从m中分配出一部分石油来弥补这个差值。若最后m依然>0，然后将这部分石油再均分即可。可是发现这个做法有很多边界case是不满足的，当最多的石油与最少的石油差值大于m时，其它国家完全没有分配，这未必是一种均衡方式。

第二个思路是采用运筹的方式来解决，因为可以动态的去搜索石油的分布，根据我们定义的score来衡量是否均衡，是否接受当前的搜索结果。同时也可以根据我们最大与最小的差值来分配两者之间的石油（此处分配是保证每个国家的石油>=最初的状态，所以不属于国家之间的调拨），让最大与最小的差值不断缩小，趋向于均衡。

score如何定义

  此处我是定义了两部分score，第一部分是任意两个国家之间的石油差值，第二部分是每个国家的石油与平均值的差值。两个score相加作为最终的score，整体的score越小表示分布的相对均衡。

算法如何设计

  我考虑采用模拟退火来作为是否接受新解，若新解满足接受条件，则接受新解，若优于当前最优解，则更新最优解。温度降到最小值之后则停止搜索，返回结果。

package main

import (
	"fmt"
	"math"
	"math/rand"
)

var r = rand.New(rand.NewSource(0)) // 用于搜索

func abs(num int) int {
	if num < 0 {
		return -num
	}
	return num
}

// 计算score
func calculateScore(nums []int) int {
	sum, res := 0, 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
		for j := i + 1; j < len(nums); j++ {
			res += abs(nums[j] - nums[i])
		}
	}
	sum /= len(nums)
	for i := 0; i < len(nums); i++ {
		res += abs(sum - nums[i])
	}
	return res
}

func dispatch(nums []int, m int) {
	T, minT, ratio := 100.0, 0.0001, 0.99 // 初始化最高温度，最低温度，降温速率

	tmp := append([]int{}, nums...)
	fix := initial(len(nums), m) // 将m分配完成
	for i := 0; i < len(nums); i++ {
		tmp[i] += fix[i]
	}
	s1 := calculateScore(tmp)          // 计算score
	bestNum := append([]int{}, tmp...) // 存储最优解
	fmt.Println(bestNum)

	for T > minT {
		iter := 500
		for iter > 0 {
			pre := append([]int{}, tmp...)

			localSearch(nums, pre) // 搜索
			s2 := calculateScore(pre)
			if s2 < s1 { // 若新解优于最优解，直接接受
				bestNum = append([]int{}, pre...)
				tmp, s1 = append([]int{}, pre...), s2
			} else if math.Exp(-float64(s2-s1)/T) < r.Float64() { // 有概率接受
				tmp, s1 = append([]int{}, pre...), s2
			}
			iter--
		}
		T *= ratio
	}
	//nums = bestNum  不会生效
	for i := 0; i < len(nums); i++ {
		nums[i] = bestNum[i]
	}
	fmt.Println(bestNum)
}

// 初始化 参数
func initial(cnt, m int) []int {
	var res []int
	for i := 0; i < cnt-1; i++ {
		num := r.Intn(m)
		m -= num
		res = append(res, num)
	}
	res = append(res, m)
	return res
}

func findMaxMin(nums []int) (int, int) {
	min, max := 1<<32-1, -1<<32
	ind1, ind2 := 0, 0

	for ind, num := range nums {
		if num > max {
			max, ind2 = num, ind
		}
		if num < min {
			min, ind1 = num, ind
		}
	}
	return ind1, ind2
}

func localSearch(nums, tmp []int) {
	minInd, maxInd := findMaxMin(tmp)
	if nums[minInd] > tmp[minInd] || nums[maxInd] > tmp[maxInd] {
		tmp = append([]int{}, nums...)
		return
	}
	if tmp[maxInd] > nums[maxInd] { // 防止r.Intn() 报错
		m := r.Intn(tmp[maxInd] - nums[maxInd])
		tmp[minInd] += m
		tmp[maxInd] -= m
	}
}

func calculateSum(nums []int) int {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	return sum
}

func main() {
	nums := []int{1, 200, 3, 4, 50}
	m := 200
	sum := m + calculateSum(nums)
	fmt.Println(nums, sum)

	dispatch(nums, m)
	fmt.Println(nums, calculateSum(nums))
}

-------------------
[1 200 3 4 50] 458  初始值
[75 272 16 28 67]
[75 201 55 60 67]
[75 201 55 60 67] 458 最终分配结果

todo

1、score的定义未必合理，可以考虑再使用更优的score，比如每个国家的涨幅。。。

2、搜索方式也可以更丰富些。