西班牙有个著名景点叫圣家堂,其中“受难立面”上主要画着耶稣从“最后的晚餐”到“升天”的场景,其中还有一个如下图所示的魔方阵,因“纵、横、对角线的数字之和都是33”而闻名(据说耶稣辞世时是 33 岁)。
如果不局限于由纵、横、对角线的数字相加,那么和数为 33 的组合有 310 种之多(网上有很多“4 个数字相加……”这样的问题,如果限定只能由 4 个数字相加,则是 88 种)。
问题:使用这个魔方阵,进行满足下列条件的加法运算,求“和相同的组合”的种数最多的和。
条件:
其实就是给定16个数中,求其中任意组合的相加和,其中得到相同的和的组合种类数最多的和。
这是基于直感想到的第一个办法(通常我会先从最naïve的方法开始着手,虽然笨拙,但是也有它的价值)。一上来就能直中靶心想到最优解毕竟不是凡人所能奢望的事情,循序渐进或许更符合普通人的步调。
针对每一个可能的和target(和的可能数为以上所有数字总和加1,把0也当作一种可能考虑,但是只考虑给定的数组中的数都为非负数的情况),扫描所有的组合,确认和为target的组合种类数。
然后比较所有可能的target对应的组合种类数。求解流程如下所示:
代码参见下面shouNanMoFang1().
解法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)就无能为力了。
这里所说的动态规划的方法是参考原书的提示。但是原书提示就是寥寥一句话“每次设置一个数。。。”。怎么肥四啊?有点类似于数学证明中的“显而易见、易证”之类的(人与人之间的脑回路的差别有这么大嘛)。查阅了几个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().
- # -*- 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个数量级!合理的算法设计的威力是如此巨大!