优化食物分配算法：最小化相邻饥饿差的方案探讨

要求实现FoodDistribution(arr)函数，数组arr格式为[N, h1, h2,...]：

• N为可分配的三明治数量，范围1-20
• hi为不同人的饥饿值，范围0-5
  目标是利用现有三明治，最小化数组中相邻两人的饥饿差总和。

尝试解法及问题 #

1. 贪心算法：循环至三明治耗尽，每次选择能使饥饿差总和最小的位置分配1个三明治，但该方法在测试用例[7,5,4,3,4,5,2,3,1,4,5]中无法得到全局最优解。
2. 暴力递归+记忆化思路：递归遍历每个位置，选择分配或不分配三明治，但不确定如何设计记忆化状态，当前时间复杂度为O(2^(n+s))，希望找到更优解法，或明确该问题是否适合用动态规划/记忆化优化。

贪心算法代码 #

def FoodDistribution(arr):
    sandwiches = arr[0]
    hunger_levels = arr[1:]

    # Function to calculate the total difference
    def total_difference(hunger_levels):
        return sum(abs(hunger_levels[i] - hunger_levels[i + 1]) for i in range(len(hunger_levels) - 1))

    def reduce_combs(combs):
        local_min = float('inf')
        local_min_comb = None
        for comb in combs:
            current_difference = total_difference(comb)
            if current_difference < local_min:
                local_min = current_difference
                local_min_comb = comb

        return local_min_comb
    # Function to distribute sandwiches
    def distribute_sandwiches(sandwiches, hunger_levels):
        global_min = total_difference(hunger_levels)
        print(global_min)
        while sandwiches > 0 and global_min > 0:
            combs = []
            for i in range(len(hunger_levels)):
                comb = hunger_levels[:]
                comb[i] -= 1
                combs.append(comb)

            local_min_comb = reduce_combs(combs)
            x = total_difference(local_min_comb)
            print( sandwiches, x, local_min_comb)
            global_min = min(global_min, x)
            hunger_levels = local_min_comb
            sandwiches -= 1
        return global_min

    # Distribute sandwiches and calculate the minimized difference
    global_min = distribute_sandwiches(sandwiches, hunger_levels)
    return global_min

if __name__ == "__main__":
    print(FoodDistribution([7, 5, 4, 3, 4, 5, 2, 3, 1, 4, 5]))

暴力递归代码 #

def FoodDistribution(arr):
    sandwiches = arr[0]
    hunger_levels = arr[1:]

    # Distribute sandwiches and calculate the minimized difference
    global_min = solve(0, sandwiches, hunger_levels)
    return global_min


def solve(index, sandwiches, hunger_levels):
    if index >= len(hunger_levels) or sandwiches == 0:
        return total_difference(hunger_levels)

    # take a sandwich
    hunger_levels[index] += -1
    sandwiches += -1
    minTake = solve(index, sandwiches, hunger_levels)
    hunger_levels[index] += 1
    sandwiches += 1

    # dont take sandwich
    dontTake = solve(index + 1, sandwiches, hunger_levels)

    return min(minTake, dontTake)


def total_difference(hunger_levels):
    return sum(abs(hunger_levels[i] - hunger_levels[i + 1]) for i in range(len(hunger_levels) - 1))

if __name__ == "__main__":
    print(FoodDistribution([7, 5, 4, 3, 4, 5, 2, 3, 1, 4, 5]))

测试用例最优状态示例 #

sandwiches = 7 
hunger = [5, 4, 3, 4, 5, 2, 3, 1, 4, 5]
最优结果为6，对应状态：
[3, 3, 3, 3, 3, 2, 2, 1, 4, 5]
[4, 3, 3, 3, 3, 2, 2, 1, 4, 4]
[4, 4, 3, 3, 2, 2, 2, 1, 4, 4]
[4, 4, 3, 3, 3, 2, 1, 1, 4, 4]
[4, 4, 3, 3, 3, 2, 2, 1, 3, 4]
[4, 4, 3, 3, 3, 2, 2, 1, 4, 4]
[5, 4, 3, 3, 3, 2, 2, 1, 3, 3]

内容的提问来源于stack exchange，提问作者Mohd Alomar