热水器与楼层问题

住在玉泉 6 舍，5 层楼装了 2 个热水器，分别在 1, 4 层

思考了一下，这样放置恰好能满足两个最优条件：

1. 每层楼的人打热水时，上下楼层最少
2. 热水器放置总楼层数之和最小，即安放成本最小

1. 两种约束，多标签最小值问题

条件 1 优先级更高，先按 1 排序，在满足 1 的情况下，再保证 2 最小
python 的 max, min, sorted 通过指定 key 可以解决此类问题

import itertools


def print_each_P_floors(floors, heater_floors):
    print('floor  heater  steps')
    for p in range(1, floors + 1):
        cand_steps = [abs(p - h) for h in heater_floors]
        min_idx = cand_steps.index(min(cand_steps))  # min steps
        if p > heater_floors[min_idx]:  # 下楼
            print('{:^5d}  {:^6d}  {:^5d}'.format(p, heater_floors[min_idx], -cand_steps[min_idx]))
        else:  # 上楼
            print('{:^5d}  {:^6d}  {:^5d}'.format(p, heater_floors[min_idx], cand_steps[min_idx]))


def best_heater_floors(floors, heaters):
    """
    热水器放置问题 两个约束条件
      1.每层楼的人 打热水 上下楼层最少
      2.热水器放置的 总楼层数之和最小 成本最小
    选择时，在能满足 1 的情况下满足 2，先按 1 排序 再按 2
    :param floors: 楼层总数
    :param heaters: 热水器数量
    :return: heater_floors 热水器放置的楼层
    """
    # 可能的放置情况，从中选取
    cand_heater_floors = list(itertools.combinations(range(1, floors + 1), heaters))
    total_step_floors = []  # idx corresponds to idx in cand_heater_floors
    for heater_floors in cand_heater_floors:
        # each heaters
        total_steps = 0  # sum of min_step of each person
        total_floors = sum(heater_floors)
        for p in range(1, floors + 1):  # 1-5
            # each person's floor - each heater's floor
            min_step = min([abs(p - h) for h in heater_floors])
            total_steps += min_step
        total_step_floors.append((total_steps, total_floors))

    # 双成本最小的
    heater_floors = cand_heater_floors[total_step_floors.index(min(total_step_floors))]
    return heater_floors


if __name__ == '__main__':
    floors, heaters = 5, 2
    heater_floors = best_heater_floors(floors, heaters)
    print('heater floors:', heater_floors)
    print_each_P_floors(floors, heater_floors)

测试 floors, heaters = 5, 2，平均每 2 人用 1 台

heater floors: (1, 4)
floor  heater  steps
  1      1       0  
  2      1      -1  
  3      4       1  
  4      4       0  
  5      4      -1 

测试 floors, heaters = 6, 2，平均每 3 人用 1 台

heater floors: (2, 5)
floor  heater  steps
  1      2       1  
  2      2       0  
  3      2      -1  
  4      5       1  
  5      5       0  
  6      5      -1 

测试 floors, heaters = 10, 3，平均每 3 人用 1 台

heater floors: (2, 5, 8)
floor  heater  steps
  1      2       1  
  2      2       0  
  3      2      -1  
  4      5       1  
  5      5       0  
  6      5      -1  
  7      8       1  
  8      8       0  
  9      8      -1  
 10      8      -2 

2. 简单方案

根据 1 的实验结果，输出有规律，有更简单的实现，1 太费时了。

def nearest_divided_number(a, b):
    assert a > b
    q, r = a // b, a % b  # 商，余数
    if r >= b / 2:  # 余数 >= 除数/2
        return a + b - r
    else:
        return a - r


def mid_val(a):
    if a % 2 == 0:
        return a // 2
    else:
        return a // 2 + 1


def better_heater_floors(floors, heaters):
    """
    划分成 楼层子区间 考虑
    """
    heater_floors = []

    nearest = nearest_divided_number(floors, heaters)  # 最近可整除的数
    sub_floors = nearest // heaters  # 楼层子区间层数
    remainder = floors - sub_floors * (heaters - 1)  # 不整除的放到1个区间
    mid_rem, mid_sub = mid_val(remainder), mid_val(sub_floors)  # 子区间放置楼层

    # 往下/往上 分配问题
    if nearest > floors:  # 上整下补
        heater_floors.append(mid_rem)  # 第1个
        for idx in range(1, heaters):  # 后 heaters - 1 个
            heater_floors.append(remainder + mid_sub + (idx - 1) * sub_floors)
    else:  # 上补下整
        for idx in range(heaters - 1):  # 前 heaters - 1 个
            heater_floors.append(mid_sub + idx * sub_floors)
        heater_floors.append(sub_floors * (heaters - 1) + mid_rem)  # 最后1个

    return heater_floors

3. 两种方案耗时比较

import time

def test_func(floors=5, heaters=2):
    print('floors, heaters:', floors, heaters)
    st = time.process_time_ns()
    heater_floors = best_heater_floors(floors, heaters)
    print('result:', heater_floors)
    print('time:', time.process_time_ns() - st)
    # print_each_P_floors(floors, heater_floors)

    st = time.process_time_ns()
    heater_floors = better_heater_floors(floors, heaters)
    print('result:', heater_floors)
    print('time:', time.process_time_ns() - st)
    # print_each_P_floors(floors, heater_floors)


if __name__ == '__main__':
    test_func(5, 2)
    test_func(8, 2)
    test_func(10, 3)
    test_func(19, 2)
    test_func(50, 3)

方案 2 明显快很多，特别是 floors 较大时，排列组合逐个比较太慢了。

floors, heaters: 5 2
result: (1, 4)
time: 202000
result: [1, 4]
time: 32000
floors, heaters: 8 2
result: (2, 6)
time: 440000
result: [2, 6]
time: 22000
floors, heaters: 10 3
result: (2, 5, 8)
time: 2830000
result: [2, 5, 8]
time: 78000
floors, heaters: 19 2
result: (5, 14)
time: 8022000
result: [5, 14]
time: 152000
floors, heaters: 50 3
result: (8, 25, 42)
time: 1443854000
result: [8, 25, 42]
time: 32000