提问人：Sharhad 提问时间：12/27/2022 最后编辑：Sharhad 更新时间：1/4/2023 访问量：754
将长度为 N 的序列切割成子序列，使每个子阵列的总和小于 M，并且切割使每个部分的最大值之和最小化
Cut a sequence of length N into subsequences such that the sum of each subarray is less than M and the cut minimizes the sum of max of each part
问：
给定一个长度为 的整数数组序列，将该序列切成几个部分，使得每个部分都是原始序列的后续子序列。a_nN
每个部件必须满足以下条件：
- 每个部分的总和不大于给定的整数
M - 找到一个最小化每个零件的最大整数之和的切割
例如：
input : n = 8, m = 17 arr = [2, 2, 2, 8, 1, 8, 2, 1]
output = 12
explanation: subarrays = [2, 2, 2], [8, 1, 8], [2, 1]
sum = 2 + 8 + 2 = 12
0 <= N <= 100000
each integer is between 0 and 1000000
如果不存在此类切入，则返回 -1
我相信这是一个动态规划问题，但我不确定如何处理这个问题。
我对编码比较陌生，在一次面试中遇到了这个问题，但我无法做到。我想知道如何解决它以备将来参考。
这是我尝试过的：
n = 8
m = 17
arr = [2, 2, 2, 8, 1, 8, 2, 1]
biggest_sum, i = 0, 0
while (i < len(arr)):
seq_sum = 0
biggest_in_seq = -1
while (seq_sum <= m and i < len(arr)):
if (seq_sum + arr[i] <= m ):
seq_sum += arr[i]
if (arr[i] > biggest_in_seq):
biggest_in_seq = arr[i]
i += 1
else:
break
biggest_sum += biggest_in_seq
if (biggest_sum == 0):
print(-1)
else:
print(biggest_sum)
这给出了结果，子序列是：16[[2, 2, 2, 8, 1], [8, 2, 1]]
答：
0赞
QuadU
1/4/2023
#1
问题是您从左到右填充每个序列，直到最大允许值。您应该评估序列长度的不同选项并最小化结果，在示例中，这意味着 2 个值必须位于同一序列中。m8
一个可能的解决方案可能是：
n = 8
m = 17
arr = [2, 2, 2, 8, 1, 8, 2, 1]
def find_solution(arr, m, n):
if max(arr)>m:
return -1
optimal_seq_length = [0] * n
optimal_max_sum = [0] * n
for seq_start in reversed(range(n)):
seq_len = 0
seq_sum = 0
seq_max = 0
while True:
seq_len += 1
seq_end = seq_start + seq_len
if seq_end > n:
break
last_value_in_seq = arr[seq_end - 1]
seq_sum += last_value_in_seq
if seq_sum > m:
break
seq_max = max(seq_max, last_value_in_seq)
max_sum_from_next_seq_on = 0 if seq_end >= n else optimal_max_sum[seq_end]
max_sum = max_sum_from_next_seq_on + seq_max
if seq_len == 1 or max_sum < optimal_max_sum[seq_start]:
optimal_max_sum[seq_start] = max_sum
optimal_seq_length[seq_start] = seq_len
# create solution list of lists
solution = []
seg_start = 0
while seg_start < n:
seg_length = optimal_seq_length[seg_start]
solution.append(arr[seg_start:seg_start+seg_length])
seg_start += seg_length
return solution
print(find_solution(arr, m, n))
# [[2, 2, 2], [8, 1, 8], [2, 1]]
我的建议的主要方面：
- 从一个小数组（只有最后一个元素）开始，让问题数组增长到前面：
[1][2, 1][8, 2, 1]- 等。
- 对于上述每个问题数组，存储：
- 每个序列的最大值 （） 的最优和 ，即要最小化的值
optimal_max_sum - 第一个序列 （） 的序列长度，以达到此最佳值
optimal_seq_length
- 每个序列的最大值 （） 的最优和 ，即要最小化的值
- 为此，请执行以下操作： 对于从问题数组开头开始的每个允许的序列长度：
- 计算新值，并将其添加到此序列之后为部件计算的先前值
max_sumoptimal_max_sum - 保留最小的，将其存储在 和相关的seq_length
max_sumoptimal_max_sumoptimal_seq_length
- 计算新值，并将其添加到此序列之后为部件计算的先前值
评论
arr[[2], [2], [2], [8], [1], [8], [2], [1]]