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

编程入门行业动态更新时间:2024-10-19 13:32:39

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

1. 问题描述

2. 解题分析

2.1 初始算法流程

2.2 优化

3. 代码及测试

4. 后记

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 npmemo   = dict()
BIGINT = 10000def cut_cake2(m:int,n:int,diff:int)->int:''' Parameters----------m : intHorizontal width of the cake.n : intVertical height of the cake.diff : intRecord the difference of eat quantity between two peoples.Returns-------intThe 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 0else:memo[(m,n,diff)] = BIGINTreturn BIGINTmincuts = BIGINT# Vertical trial Cutfor x in range(1,m//2+1): new_m = m-x # Keep the larger partnew_n = neat_smaller = n * xcutlen = n + cut_cake2(new_m,new_n,eat_smaller - diff)if mincuts > cutlen:mincuts = cutlen# Horizontal trial cutfor y in range(1,n//2+1):new_m = mnew_n = n-y  # Keep the larger parteat_smaller = m * ycutlen = m + cut_cake2(new_m,new_n,eat_smaller - diff)if mincuts > cutlen:mincuts = cutlen            memo[(m,n,diff)] = mincutsreturn mincutsM = 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)