最近做过一到面试题,做了好久都没思路,现在将其整理一下:
题目如下: 任意一组正整数(2N),将其均分为两组数(即每组数N个) A1 A2,求这两组数差的最小值(即 |sum(A1)-sum(A2)| 的最小值 )
当时的思路如下:
例如 有10个数,先将他分为 5个数一组的两组数
感觉这是一个简单的组合问题,就是从10个数中选取5个数,保证这个选中的5个数的和尽可能的接近这10个数的和的一半,这样另外5个数的和也会接近这10个数的和的一半,那么这样这两组数的差就会最小
1. 先创建一个数组(python)
n=10
r = Random()
an = [ r.randint(1,100) for i in range(0,n)]
2. 利用for循环 从这10个数中选取不重复的5个数(这里的不重复不是指值不能重复而是索引不能重复即不能将同一个数选取2次)
'''
for循环实现 和差最小
'''
import copy
from random import Random
n = 10
random = Random()
an = [random.randint(1, 100) for i in range(0, n)]
_sum = sum(an)
half_sum = _sum / 2
print('数组:{},和:{},和的一半:{}'.format(an, _sum, half_sum))
rs = []
for i1 in range(0, n):
for i2 in range(0, n):
if i2 != i1:
for i3 in range(0, n):
if i3 != i1 and i3 != i2:
for i4 in range(0, n):
if i4 != i1 and i4 != i2 and i4 != i3:
for i5 in range(0, n):
if i5 != i1 and i5 != i2 and i5 != i3 and i5 != i4:
arr = [an[i1], an[i2], an[i3], an[i4], an[i5]]
_arr_sum = sum(arr)
if _arr_sum <= half_sum:
rs.append({'arr': arr, 'sum': _arr_sum})
maxItem = max(rs, key=lambda x: x['sum'])
copyItem = copy.deepcopy(maxItem['arr'])
otherItem = {'arr': [], 'sum': _sum - maxItem['sum']}
for i in an:
if i in copyItem:
copyItem.remove(i)
else:
otherItem['arr'].append(i)
print('均分为两个数组:{},{}'.format(maxItem,otherItem))
3. 这样虽然可以得到一个答案,但是不具有拓展性,比如n=12,n=14时,这时代码就得跟着改变,而且for 和 if 太多,后续自己都可能看不清,所以考虑使用递归来解决:
'''
递归实现
'''
def digui(n):
import copy
from random import Random
random = Random()
an = [random.randint(1, 100) for i in range(0, n)]
_sum = sum(an)
half_sum = _sum / 2
k = int(n / 2)
print('数组:{},和:{},和的一半:{}'.format(an, _sum, half_sum))
rs = []
def permutation(ies):
for i in range(0, n):
if i not in ies:
if len(ies) + 1 == k:
arr = [an[i]]
for j in ies:
arr.append(an[j])
_arr_sum = sum(arr)
if _arr_sum <= half_sum:
rs.append({'arr': arr, 'sum': _arr_sum})
else:
ies_copy = copy.deepcopy(ies)
ies_copy.append(i)
permutation(ies=ies_copy)
permutation(ies=[])
maxItem = max(rs, key=lambda x: x['sum'])
copyItem = copy.deepcopy(maxItem['arr'])
otherItem = {'arr': [], 'sum': _sum - maxItem['sum']}
for i in an:
if i in copyItem:
copyItem.remove(i)
else:
otherItem['arr'].append(i)
print('均分为两个数组:{},{}'.format(maxItem, otherItem))
这样虽然也能实现解决该问题,并且实现了拓展性,改变n,不需要改变代码,但是测试性能方向随着n的扩大,运算时间急速膨胀.....
数组:[55, 13, 55, 26, 42, 51, 62, 31],和:335,和的一半:167.5
均分为两个数组:{'arr': [31, 55, 55, 26], 'sum': 167},{'arr': [13, 42, 51, 62], 'sum': 168}
n=8,耗时:0.014919519424438477秒
数组:[67, 36, 20, 30, 87, 10, 84, 10, 98, 96],和:538,和的一半:269.0
均分为两个数组:{'arr': [98, 67, 10, 84, 10], 'sum': 269},{'arr': [36, 20, 30, 87, 96], 'sum': 269}
n=10,耗时:0.07349681854248047秒
数组:[99, 31, 80, 72, 76, 92, 38, 24, 46, 45, 41, 74],和:718,和的一半:359.0
均分为两个数组:{'arr': [41, 99, 31, 72, 92, 24], 'sum': 359},{'arr': [80, 76, 38, 46, 45, 74], 'sum': 359}
n=12,耗时:2.190526008605957秒
数组:[95, 39, 9, 43, 7, 31, 61, 25, 56, 70, 3, 41, 54, 78],和:612,和的一半:306.0
均分为两个数组:{'arr': [3, 95, 39, 9, 43, 61, 56], 'sum': 306},{'arr': [7, 31, 25, 70, 41, 54, 78], 'sum': 306}
n=14,耗时:84.05565357208252秒
4 那有没有其他实现可以改善时间复杂度了,接下来就是我要介绍的主角出场,那么是什么呢?动态规划
动态规划最紧要的就是要推出动态规划表达式,下面是推导过程=>
数组 [1,2,3,4,5]
从 数组 中 选取 2 个数 即 从五个数中选取2个数,情况如下:
[1,2] [1,3] [1,4] [2,3] [2,4] [3,4] [1,5] [2,5][3,5][4,5]
可以看到他可以分为两个部分: 前面6种情况 和从数组[1,2,3,4] 中选取2个数字的情况相同 后面可以看做从数组[1,2,3,4] 中选取一个数组与5 组合
故 表达式推导如下:
数组[a1,a2,...an] 数组的长度为n , 从中选取i 个数 0<i <=n
表达式如下:
dp[n][i] = [ [a1] ,[a2],.....[an] ] i=1
= dp[n-1][i] U { ai => dp[n-1][i-1] } n>1 这里 U代表并集运算 => 代表 组合
这里有可能存在 n-1<i 存在的情况 即可能出现从 3 个数中选取 4 个数的情况 因而表达式需要改为:
dp[n][i] = [ [a1] ,[a2],.....[an] ] i=1
= dp[n-1][i] U { ai => dp[n-1][i-1] } n>1 and i <= n-1
= { ai => dp[n-1][i-1] } n>1 and i>n-1
测试如下:
数组:[69, 100, 90, 89, 45, 26, 25, 36],和:480,和的一半:240.0
均分为两个数组:{'arr': [69, 26, 36, 45], 'sum': 176},{'arr': [0, 25, 89, 90, 100], 'sum': 304}
n=8,耗时:0.0013966560363769531秒
数组:[89, 48, 37, 34, 56, 45, 34, 49, 65, 64],和:521,和的一半:260.5
均分为两个数组:{'arr': [49, 34, 37, 45, 48], 'sum': 213},{'arr': [0, 34, 56, 64, 65, 89], 'sum': 308}
n=10,耗时:0.008600234985351562秒
数组:[27, 51, 96, 53, 15, 3, 34, 33, 63, 28, 61, 10],和:474,和的一半:237.0
均分为两个数组:{'arr': [34, 10, 15, 27, 28, 33], 'sum': 147},{'arr': [0, 3, 51, 53, 61, 63, 96], 'sum': 327}
n=12,耗时:0.016797780990600586秒
数组:[25, 89, 38, 54, 4, 41, 17, 79, 17, 7, 59, 60, 35, 35],和:560,和的一半:280.0
均分为两个数组:{'arr': [38, 7, 17, 17, 25, 35, 35], 'sum': 174},{'arr': [0, 4, 41, 54, 59, 60, 79, 89], 'sum': 386}
n=14,耗时:0.06400394439697266秒
数组:[38, 58, 1, 56, 41, 69, 44, 45, 70, 95, 75, 49, 1, 83, 12, 38],和:775,和的一半:387.5
均分为两个数组:{'arr': [49, 1, 12, 38, 38, 41, 44, 45], 'sum': 268},{'arr': [0, 1, 56, 58, 69, 70, 75, 83, 95], 'sum': 507}
n=16,耗时:0.3163731098175049秒
数组:[2, 65, 18, 61, 92, 79, 82, 51, 100, 52, 26, 53, 70, 87, 47, 30, 66, 52],和:1033,和的一半:516.5
均分为两个数组:{'arr': [61, 18, 26, 30, 47, 51, 52, 52, 53], 'sum': 390},{'arr': [0, 2, 65, 66, 70, 79, 82, 87, 92, 100], 'sum': 643}
n=18,耗时:1.3240556716918945秒
代码如下:
def dynamic_development(n):
import copy
from random import Random
random = Random()
an = [random.randint(1, 100) for i in range(0, n)]
_sum = sum(an)
half_sum = _sum / 2
k = int(n / 2)
print('数组:{},和:{},和的一半:{}'.format(an, _sum, half_sum))
# 这里一定要排序,否则可能会有问题
an = [0] + sorted(an)
dp = [['' for j in range(0, min(k + 1, i + 1))] for i in range(0, n + 1)]
for i in range(1, n + 1):
for j in range(1, min(k + 1, i + 1)):
if i == 0 or j == 0:
dp[i][j] = [{'arr': [], 'sum': 0}]
elif j == 1:
ps = []
for m in range(1, i + 1):
ps.append({'arr': [an[m]], 'sum': an[m]})
dp[i][j] = ps
else:
ps = []
if j <= i - 1:
ps = ps + dp[i - 1][j]
for item in dp[i - 1][j - 1]:
_arr_sum = an[j] + item['sum']
if _arr_sum <= half_sum:
arr_copy = copy.deepcopy(item['arr'])
arr_copy.append(an[j])
ps.append({'arr': arr_copy, 'sum': _arr_sum})
dp[i][j] = ps
#print('dp[{}][{}]={}'.format(i, j, dp[i][j]))
#print('dp[n][k] ={} '.format(dp[n][k]))
maxItem = max(dp[n][k], key=lambda x: x['sum'])
copyItem = copy.deepcopy(maxItem['arr'])
otherItem = {'arr': [], 'sum': _sum - maxItem['sum']}
for i in an:
if i in copyItem:
copyItem.remove(i)
else:
otherItem['arr'].append(i)
print('均分为两个数组:{},{}'.format(maxItem, otherItem))
网友评论