程序员的算法趣题Q20: 受难立面魔方阵

1. 问题描述

西班牙有个著名景点叫圣家堂，其中“受难立面”上主要画着耶稣从“最后的晚餐”到“升天”的场景，其中还有一个如下图所示的魔方阵，因“纵、横、对角线的数字之和都是33”而闻名（据说耶稣辞世时是 33 岁）。

如果不局限于由纵、横、对角线的数字相加，那么和数为 33 的组合有 310 种之多（网上有很多“4 个数字相加……”这样的问题，如果限定只能由 4 个数字相加，则是 88 种）。

问题：使用这个魔方阵，进行满足下列条件的加法运算，求“和相同的组合”的种数最多的和。

条件：

1. 不限于由纵、横、对角线上的数字相加
2. 加数的个数不限于4

其实就是给定16个数中，求其中任意组合的相加和，其中得到相同的和的组合种类数最多的和。

2. 解法1--笨办法

这是基于直感想到的第一个办法（通常我会先从最naïve的方法开始着手，虽然笨拙，但是也有它的价值）。一上来就能直中靶心想到最优解毕竟不是凡人所能奢望的事情，循序渐进或许更符合普通人的步调。

针对每一个可能的和target（和的可能数为以上所有数字总和加1，把0也当作一种可能考虑，但是只考虑给定的数组中的数都为非负数的情况），扫描所有的组合，确认和为target的组合种类数。

然后比较所有可能的target对应的组合种类数。求解流程如下所示：

代码参见下面shouNanMoFang1().

3. 解法2--逆向思维

解法1太慢了，在nums数组中为16个数时就需要秒级的时间。16个数的所有可能长度的组合数是多少呢？恰好是二项式公式，如下所示：

Nums中的数为16个时不过65536种组合，如果魔方阵为5*5=25是，组合数将变为，比4*4=16的情况增大了512倍，显然按解法1是无法承受的。

解法1的问题在于，以target为着眼点，对每一个target都进行了全组合扫描，这导致巨大的浪费。如果反过来看的话，其实只需要进行一遍全组合扫描，针对每一个组合根据其和给对应target的计数器进行计数即可！这样运行时间就缩短为(1/sum(nums))了。

在以下代码中用哈希表（python dict）来记录对应各可能target的组合数计数器。

其中从字典中所存储的{key: numeric value}中寻找拥有最大value的key的处理可以参考：Python tips 。

代码参见下面shouNanMoFang2().

虽然解法2相比解法1有约两个数量级的效率提升，但是在5*5魔方阵（即25个数）的情况下仍然需要数十秒的时间。对于更大的魔方阵（比如说6*6）就无能为力了。

4. 解法3--动态规划

这里所说的动态规划的方法是参考原书的提示。但是原书提示就是寥寥一句话“每次设置一个数。。。”。怎么肥四啊？有点类似于数学证明中的“显而易见、易证”之类的（人与人之间的脑回路的差别有这么大嘛）。查阅了几个CSDN博客上的解也基本上就是直接上了一段代码。。。肝疼。。。（copy一段代码很简单，或者把ruby代码翻译成别的语言的代码也很简单）不过我还是希望能用自己的话把这个事情说清楚。本题的动态规划解法的要点如下：

按顺序考虑魔方阵（代码中的nums）的每个数的处理。

令targetCnt为一个2维数组（或者说一张表格—是的，动态规划的最基本的方法就是填表！），记录在使用nums不同子集时所有可能和值targetSum的组合种类数。targetCnt[k, m]代表只考虑nums中前k+1个数（即{nums[0],…, nums[k]}）的条件下的和为m的组合种类数。

假设已经处理完nums[0],…, nums[k-1]了。当前targetCnt[k-1,:]的内容相当于是只考虑{nums[0],…, nums[k-1]}的所有可能组合所得到的结果。接下来追加考虑nums[k]，很显然，对于targetSum=m而言，只考虑{nums[0],…, nums[k-1]}且和等于(m-nums[k])的所有组合再加上nums[k]就构成了和为m的组合了，由此可以得到递推关系式如下(为了让公式简洁一些，将第1个坐标用作下标，第2个坐标用作上标)：

这样，本题的解题过程就变成了经典的动态规划填表的过程了。进一步，与一般的动态规划问题比如背包问题中不同的是，本问题中只依赖于，而且，因此我们事实上并不需要维护一张2维的表格，而只需要维护一个1维的数组就可以了。只不过需要注意，在更新tangetCnt时要按上标从大到小更新。

最后，作为动态规划解法，当然必须要定义初始条件或者边界条件。本题的边界条件可以定义为，在空组合（或者说从nums中选择0个数）时，targetSum=0时的组合数为1，targetSum>0时的组合数为0，即：

代码参见以下shouNanMoFang3().

5. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Sep  9 17:45:33 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

class Solution:
    def shouNanMoFang1(self, nums: List):
        totalSum = sum(nums)
        # cnts     = []
        targetSum   = 0  # The target sum which has the greatest number of combination sum
        targetCnt   = 0  # The number combination sum of the target sum
     
        for target in range(1,totalSum+1):
            cnt  = 0
            # ansLst = []
        
            for k in range(1,len(nums)+1):
                # print('k = ',k)
                for p in it.combinations(nums,k):
                    p_sum = sum(p)
                    if p_sum == target:
                        cnt += 1
                        # ansLst.append(p)
            if cnt > targetCnt:
                targetCnt = cnt
                targetSum = target
            # cnts.append(cnt)
        return targetSum,targetCnt

    def shouNanMoFang2(self, nums: List):
        
        numCombSum = dict()
        for k in range(1,len(nums)+1):
            for p in it.combinations(nums,k):
                p_sum = sum(p)
                if sum(p) in numCombSum:
                    numCombSum[sum(p)] += 1
                else:
                    numCombSum[sum(p)] = 1
        targetSum = max(numCombSum, key=numCombSum.get)
        targetCnt = numCombSum[targetSum]        
        return targetSum,targetCnt

    def shouNanMoFang3(self, nums: List):
        totalSum     = sum(nums)
        targetCnt    = [0] * (totalSum + 1)
        targetCnt[0] = 1
    
        for n in nums:
            for i in range(totalSum - n, -1, -1):
                targetCnt[i + n] += targetCnt[i]
    
        maxtargetCnt = max(targetCnt)
        return targetCnt.index(maxtargetCnt),maxtargetCnt

if __name__ == '__main__':        
            
    sln    = Solution()   

    nums     = [1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15]
    tStart = time.perf_counter()
    targetSum, targetCnt = sln.shouNanMoFang1(nums)
    tCost  = time.perf_counter() - tStart    
    print('Solution1: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
          .format(len(nums),targetSum,targetCnt,tCost))                                        
    
    tStart = time.perf_counter()
    targetSum, targetCnt = sln.shouNanMoFang2(nums)
    tCost  = time.perf_counter() - tStart    
    print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
          .format(len(nums),targetSum,targetCnt,tCost))      

    tStart = time.perf_counter()
    targetSum, targetCnt = sln.shouNanMoFang3(nums)
    tCost  = time.perf_counter() - tStart    
    print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
          .format(len(nums),targetSum,targetCnt,tCost))      
            
    nums     = [1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15,34,19,21,44,12,31,47,13,41]    
    tStart = time.perf_counter()
    targetSum, targetCnt = sln.shouNanMoFang2(nums)
    tCost  = time.perf_counter() - tStart    
    print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
          .format(len(nums),targetSum,targetCnt,tCost))      

    tStart = time.perf_counter()
    targetSum, targetCnt = sln.shouNanMoFang3(nums)
    tCost  = time.perf_counter() - tStart    
    print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
          .format(len(nums),targetSum,targetCnt,tCost))      
        
    nums     = [1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15,34,19,21,44,12,31,47,13,41,\
                2,15,17,5,12,37,26,19,28,20,30]    
    tStart = time.perf_counter()
    targetSum, targetCnt = sln.shouNanMoFang3(nums)
    tCost  = time.perf_counter() - tStart    
    print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
          .format(len(nums),targetSum,targetCnt,tCost))   

运行结果如下：

从运行结果可以看出，解法2相比解法1有2个数量级的提升，解法3相比解法2进一步提升了4个数量级！合理的算法设计的威力是如此巨大！