每周一课：L17 Dynamic programming (17
0.png
P17.2 MinAbsSum
Given array of integers, find the lowest absolute sum of elements.
-
P17.2 最小绝对和值
给定数组，计算对应元素乘积和的绝对值中的最小值
对于由N个整数组成的数组A和长度N的数组S，其中S的元素在集合{-1, 1}中，按照下面式子定义val(A, S)：
val(A, S)=|sum[A[i]*S[i] for i = 0..N−1]|
对于给定的数组A，在所有可能的S中，寻找val(A, S)的最小值。
编写函数：
def solution(A)
给定N个整数组成的数组A，从集合{−1，1}中任意选取N个元素，构成的所有S中，计算val(A, S)的最小值。
例如，给定的数组A：
A[0]=1，A[1]=5，A[2]=2，A[3]=-2。函数应该返回0，因为当S=[−1，1，−1，1]时，val(A, S)=0，这是最小值。
假定：
- N是区间[0，20000]内的整数；
- 数组A的每个元素都是区间[-100，100]内的整数；
- 解题思路
不能直接使用动态规划方法。因为如果不是对整个数组计算最小值，得到的结果是不正确的。需要换个思路，首先把数组A中的所有元素都变为非负数(这个操作不会影响最终的结果)，。在按照题目中的意思，每个元素乘以1或者-1，就相当于把数组中的元素分为2部分(乘以1的看作一部分a，乘以-1的看作一部分b)，只要这2部分的和值越接近，得到的结果就越小。假设转换后的数组A的元素和为S，也就是每一部分的和值不大于S/2，并且越接近越好。
下面的问题就是，在数组A中挑选元素，使得其和值最接近S/2。解决此问题可利用动态规划的思想，并且和背包问题中的01背包类似。可以将转换后的数组A看作背包问题中的重量和价值。S/2看作背包的最大承重。但是时间复杂度不满足要求，见函数solution_zero_one。根据题目中假定的内容，可知数组A中可能存在很多的重复元素，因此可以将问题转化为多重背包问题，得到的结果依然不满足要求，见函数solution_multiple。
重新思考问题，因为最终结果的最大值为数组A经过非负转换后的和值，最小值为0。定义部分a的和值为C，可知C的值位于区间[0, sum(A)]。现在定义一个序列T=[0]*(sum(A)+1)，T[i]如果大于0，说明a的和值可以为i。现在的问题就是如何构建序列T，见函数solution_nomal，可看出时间复杂度依然没有变化，因此需要进一步的优化。
遍历数组A(时间复杂度为O(N))的同时，在遍历数组A的和值(时间复杂度为O(N*max(A))，因此最终的时间复杂度为O(N**2* max(abs(A)))。现在的问题是如何降低时间复杂度。考虑到数组A存在重复的元素，因此不需要遍历整个数组A，只需要从0开始遍历到数组A的最大值即可。如果一个数不在数组A中，则不用考虑，如果在数组A中，具体见函数solution。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 17：Dynamic programming
# P 17.2 MinAbsSum
def zero_one_pack(weight, value, max_weight): # 0-1背包
"""
返回总重量不超过MW的前提下，可以获得的最大价值(在本问题中，因为价值和重量是一样的，因此也可看作获得最接近MW的重量)
:param weight: 重量数组
:param value: 价值数组
:param max_weight: 最大的重量
:return: 可以获得的最大重量
"""
# 存储最大价值的一维数组
value_list = [0] * (max_weight + 1)
# 开始计算
for ii in range(len(weight)): # 从第一个物品
copy_value = value_list.copy()
for jj in range(max_weight + 1): # 从重量0
if jj >= weight[ii]: # 如果剩余的重量大于物品重量
copy_value[jj] = max(value_list[jj - weight[ii]] + value[ii], value_list[jj]) # 选中第ii个物品和不选中，取大的
value_list = copy_value.copy() # 更新
return value_list[-1]
def solution_zero_one(A):
"""
针对数组A，寻找一个由1和-1组成的数组，使得两个数组对应元素乘积和的绝对值最小
转化为01背包问题，时间复杂度：:O(N**2 * max(abs(A)))
:param A: 数组A
:return: 返回最小的绝对值
"""
A = [abs(i) for i in A] # 将数组A的全部元素转为非负数
sum_num = sum(A) # 数组A的元素之和
max_weight = sum_num // 2 # 将数组A分为2部分，每一部分的和值需要最接近这个值
max_sum = zero_one_pack(A, A, max_weight) # 价值数组就是重量数组，获得最大价值就是获得最接近max_weight的最大重量
return sum_num - 2 * max_sum
################################################################################
def multiple_pack(weight, value, count, max_weight): # 多重背包
# 存储最大价值的一维数组
value_list = [0] * (max_weight + 1)
# 开始计算
for ii in range(len(weight)): # 从第一个物品
copy_value = value_list.copy()
for jj in range(max_weight + 1): # 从重量0
if jj >= weight[ii]: # 如果剩余的重量大于物品重量
for gg in range(count[ii] + 1): # 限制数量
if gg * weight[ii] <= jj:
copy_value[jj] = max(value_list[jj - gg * weight[ii]] + gg * value[ii], copy_value[jj])
value_list = copy_value.copy() # 更新
return value_list[-1]
def solution_multiple(A):
"""
针对数组A，寻找一个由1和-1组成的数组，使得两个数组对应元素乘积和的绝对值最小
转化为多重背包问题，时间复杂度：:O(N**2 * max(abs(A)))
:param A: 数组A
:return: 返回最小的绝对值
"""
A = [abs(i) for i in A] # 将数组A的全部元素转为非负数
weight = list(set(A))
value = list(set(A))
count = [A.count(j) for j in weight]
sum_num = sum(A) # 数组A的元素之和
max_weight = sum_num // 2 # 将数组A分为2部分，每一部分的和值需要最接近这个值
max_sum = multiple_pack(weight, value, count, max_weight)
return sum_num - 2 * max_sum
#########################################################################
def solution_normal(A):
"""
针对数组A，寻找一个由1和-1组成的数组，使得两个数组对应元素乘积和的绝对值最小
时间复杂度：:O(N**2 * max(abs(A)))
:param A: 数组A
:return: 返回最小的绝对值
"""
if len(A) == 0:
return 0
elif len(A) == 1:
return abs(A[0])
A = [abs(i) for i in A] # 将数组A的元素转为非负数
sum_num = sum(A)
sign = [0] * (sum_num // 2 + 1) # 存储否可以达到数值的标识，不大于S/2
for j in A:
if j <= sum_num // 2: # 只有小于等于S/2的才计算
sign_copy = sign.copy() # 防止同一个数重复加
for h in range(len(sign)):
if sign[h] == 1:
try:
sign_copy[h + j] = 1
except IndexError:
pass
sign_copy[j] = 1
sign = sign_copy.copy()
for k in range(sum_num // 2, -1, -1): # 从大到小开始，只要能达到，就返回
if sign[k] == 1:
return sum_num - 2 * k
################################################################################
def solution(A):
"""
针对数组A，寻找一个由1和-1组成的数组，使得两个数组对应元素乘积和的绝对值最小
时间复杂度：:O(N * max(abs(A))**2)
:param A: 数组A
:return: 返回最小的绝对值
"""
if len(A) == 0:
return 0
elif len(A) == 1:
return abs(A[0])
A = [abs(i) for i in A] # 将数组A的元素转为非负数
max_num = max(A)
sum_num = sum(A)
count = [0] * (max_num + 1)
for i in range(len(A)): # 统计每个元素出现的次数
count[A[i]] += 1
sign = [0] + [-1] * sum_num # 存储从0到最大值中的每个值是否可以达到的标识
for h in range(1, max_num + 1):
if count[h] > 0: # 说明有这个数
for j in range(sum_num):
if sign[j] >= 0:
sign[j] = count[h]
elif j >= h and sign[j - h] > 0: # 说明数字j也可以得到
sign[j] = sign[j - h] - 1 # 从h到达j消耗了一个j-h
for i in range(sum_num // 2, -1, -1): # 需要最接近sum_num // 2
if sign[i] >= 0: # 说明i这个数可以达到
return sum_num - 2 * i
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
