合约广告（二）：库存分配

package hwm

import "sort"

// Demand 广告需求
type Demand struct {
   Id          int32
   Value       int64     // 需要的流量
   Priority    float64   // 求解播放概率时的优先级
   Supplies    []*Supply // 可供给该广告的所有supply
   Probability float64   // 播放概率，HWM算法的结果
}

// Supply 流量供给
type Supply struct {
   Id          int32
   Value       int64 // 总库存
   RemainValue int64 // 剩余库存，初始时与总库存相等
}

func HWM(demands []*Demand) {
   if len(demands) == 0 {
      return
   }
   // 计算demand的priority，并以此逆序排序
   for _, demand := range demands {
      var sum int64
      for _, supply := range demand.Supplies {
         sum += supply.RemainValue
      }
      demand.Probability = float64(demand.Value) / float64(sum)
   }
   sort.Slice(demands, func(i, j int) bool {
      return demands[i].Probability > demands[j].Probability
   })

   demand := demands[0]
   demand.Probability = solveProb(demand, demand.Supplies)
   // 更新supply的RemainValue
   for _, supply := range demand.Supplies {
      supply.RemainValue -= int64(float64(supply.Value) * demand.Probability)
      supply.RemainValue = max(supply.RemainValue, 0)
   }
   // 计算下一个demand
   HWM(demands[1:])
}

func solveProb(demand *Demand, supplies []*Supply) float64 {
   /**
   求解方程：demand value = sum(min(supply_i remain_value, 播放概率p * supply_i value))
   有两种求解方式：
   1. 根据每个supply，构造一个分段函数，这种方式比较麻烦。
   2. p的取值范围为[0, 1]，我们直接对p通过二分查询求解
   */
   left, right := 0.0, 1.0
   // 二分查找20次，p的精度可以精确到百万分之一了
   for i := 0; i < 20; i++ {
      p := (left + right) / 2
      var sum int64
      for _, supply := range supplies {
         sum += min(int64(float64(supply.Value)*p), supply.RemainValue)
      }
      diff := sum - demand.Value
      // 误差小于10 就认为找到结果了
      if abs(diff) < 10 {
         return p
      }
      if diff > 0 {
         right = p
      } else {
         left = p
      }
   }
   return 0
}

func abs(i int64) int64 {
   if i < 0 {
      return -i
   }
   return i
}

func min(i, j int64) int64 {
   if i < j {
      return i
   }
   return j
}

func max(i, j int64) int64 {
   if i > j {
      return i
   }
   return j
}