您当前的位置：首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q55: 平分蛋糕

时间：12-31来源：作者：点击数：

1. 问题描述

2. 解题分析

这个题目第一感就是动态规划。

对于（m, n）形状（如下图所示，m代表横向的长度，n代表纵向的高度）。为了方便起见，参照以下图右上角这样的坐标说明。

每切一刀并吃掉小的那一块后留下的仍然是一个长方形。

但是由于需要确保从头到尾两个人分到的蛋糕一样多，所以子问题并不单纯由长方形的尺寸决定。还要考虑进去当前轮到谁切，以及两个各自已经分到的蛋糕大小。

2.1 初始算法流程

考虑“递归+Memoization”的实现方式，得到算法流程如下所示。

初始状态为who=0, eat=[0,0]，因此调用search(M,N,0,0,0)即可。

2.2 优化

进一步考虑优化。

【优化1】

由于总是吃掉较小的那一块。

因此，比如说纵向切的时候，x=1与x=(m-1)其实是等价的。横向切的情况也同理。这样切分的次数可以大约减小一半。

【优化2】

最终只关心两者分到的是不是相同，并不需要关心各自分到的绝对量（当然在本题中两者平分的话所分的量也是确定的），因此可以用一个变量diff来去掉eat[2]。在跟踪统计diff时，第1个人的份加进去，第2个人的份则减掉，即可。

进一步，考虑每一步分掉的量为z，每一步用(diff = z – diff)的方式跟踪的话，连who(表示当前轮到谁切分)都可以省掉了。这是原题解给出的技巧，确实小巧精致！

【优化3】

由于对称性，(m,n)与(n,m)两种形状其实也是等价的，由此可以进一步减少需要计算的子问题个数。比如说M=8,N=4与M=4,N=8其实是相同的，只不过一个是横着放，另一个是直着放。因此可以籍此减少一半的搜索。体现为以下这条语句：

m, n = (n,m) if n>m else (m,n)

考虑以上优化策略后，得到以下代码。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Oct 14 07:49:38 2021

@author: chenxy
"""

# import sys
import time
# import datetime
# import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque
import itertools as it
import numpy as np

memo   = dict()
BIGINT = 10000

def cut_cake2(m:int,n:int,diff:int)->int:
    ''' 
    Parameters
    ----------
    m : int
        Horizontal width of the cake.
    n : int
        Vertical height of the cake.
    diff : int
        Record the difference of eat quantity between two peoples.

    Returns
    -------
    int
        The minimal cut length, starting from the current state.
    '''
    global memo
    # print('cut_cake:', m,n,who)
    m, n = (n,m) if n>m else (m,n)
    if (m,n,diff) in memo:
        return memo[(m,n,diff)]
    if m==1 and n==1: # Reach the goal.
        if diff == 1:
            return 0
        else:
            memo[(m,n,diff)] = BIGINT
            return BIGINT
    
    mincuts = BIGINT
    # Vertical trial Cut
    for x in range(1,m//2+1): 
        new_m = m-x # Keep the larger part
        new_n = n
        eat_smaller = n * x
        cutlen = n + cut_cake2(new_m,new_n,eat_smaller - diff)
        if mincuts > cutlen:
            mincuts = cutlen
    # Horizontal trial cut
    for y in range(1,n//2+1):
        new_m = m
        new_n = n-y  # Keep the larger part
        eat_smaller = m * y
        cutlen = m + cut_cake2(new_m,new_n,eat_smaller - diff)
        if mincuts > cutlen:
            mincuts = cutlen            
    memo[(m,n,diff)] = mincuts
    return mincuts

M = 16
N = 12
tStart = time.perf_counter()
mincuts = cut_cake2(M,N,0)
tCost  = time.perf_counter() - tStart
print('M={0}, N={1}, mincuts={2}, tCost = {3:6.3f}(sec)'.format(M,N,mincuts,tCost))

运行结果：

M=16, N=12, mincuts=47, tCost = 0.036(sec)

M=30, N=30, mincuts=107, tCost = 1.751(sec)