给定N个正整数的数组。设最小元素为L,所有元素的总和为S.修改子集合
我需要找出是否对于每个整数X(其中X介于L和S之间)可以选择数组的子集该元件的该子集中的总和等于X.
例:
让N=5
和阵列是{4,8,2,1,16}
。那么这里所有的元素都可以在1到31之间,所以这里的答案是“是”。
如果假设N=4
和数组是{5,1,2,7}
。然后,对于1到15之间的值,不能进行值4和11。 所以这里回答是“不”。
给定N个正整数的数组。设最小元素为L,所有元素的总和为S.修改子集合
我需要找出是否对于每个整数X(其中X介于L和S之间)可以选择数组的子集该元件的该子集中的总和等于X.
例:
让N=5
和阵列是{4,8,2,1,16}
。那么这里所有的元素都可以在1到31之间,所以这里的答案是“是”。
如果假设N=4
和数组是{5,1,2,7}
。然后,对于1到15之间的值,不能进行值4和11。 所以这里回答是“不”。
我知道发现不能用这个数组返回的最小数目,但不知道如何解决这个问题
第一,请问该数组只有一个元素?如果是这样,答案是肯定的。
否则,找到最小不可能的总和。它比S大吗?如果是这样,答案是肯定的。否则,答案是否定的。 (如果最小值小于L,则数组不包含1,并且S-1是不可能的总和。)
要查找最低不可能的总和,我们对输入进行排序,然后找到最低不可能的总和数组的每个前缀。在Python:通过感应
def lowest_impossible_sum(nums):
nums = sorted(nums)
partial_sum = 0
for num in nums:
if num > partial_sum + 1:
return partial_sum + 1
partial_sum += num
return partial_sum + 1
证明正确性:
设A是排序后的数组。如果A[0] > 1
,那么1是不可能的最低总和。否则,A[:1]
的元素可以产生高达sum(A[:1])
的所有总和。
假设归纳法,可以选择A[:k]
的子集来产生所有总和为sum(A[:k])
的总和。
A[k] > sum(A[:k]) + 1
,那么sum(A[:k]) + 1
是不可能的最低总和;它不能由A[:k]
的子集生成,并且添加不在A[:k]
中的元素将无济于事,因为它们都太大。A[k] <= sum(A[:k]) + 1
,那么A[:k+1]
的子集可以产生高达sum(A[:k+1])
的每个和。达到sum(A[:k])
的每个总和已经可以通过归纳假设产生,并且从sum(A[:k]) + 1
到sum(A[:k+1])
的总和可以通过选择A[k]
和合适的子集A[:k]
加起来得到。设x是第一个索引,例如A[x] > sum(A[:x]) + 1
或len(A)
如果没有这样的索引。通过归纳,每个总计可达sum(A[:x])
。但是,无论是因为x超过了数组的尾数还是因为A[x] > sum(A[:x]) + 1
,都无法产生总和sum(A[:x]) + 1
。因此,我们只需要搜索x并返回sum(A[:x]) + 1
。这就是算法的作用。
可否请您提供一个有效的算法,因为根据我的算法,我将检查从一个开始的每个数字,对于大型的N – user3219308
@ user3219308来说效率太低:那么,找到最低不可能总和的算法相当低效。我将用一种应该能够快速解决这两个问题的算法进行编辑。 – user2357112
还有一个问题,最小数目可能小于L.但是,我99.9%相信,如果1不在数组中,并且数组包含多于1个元素 - 则无法获得全部总和。 (这个声明需要证明!)。然而,这个解决方案在arr = [5]中失败了,例如,无法实现的最小元素是1,答案仍然是'是'。 – amit
首先对数组中的所有元素进行排序。如果你想从数组的元素中得到L和S之间的所有值,那么L = 1并且元素应该是2^i的形式。最大的元素可能不是形式2^i,因为总和不必是形式(2^i - 1)。
查看阿米特的反例。 – user2357112
@ user2357112:谢谢指出。现在我纠正了算法。最伟大的元素可能不是形式2^i。 –
仍然错误。 “{1,1,1}”是我认为你想说的一个反例。 – user2357112
你需要提供你所尝试过的。 – herohuyongtao
@harold No. {1,2,3}是一个反例。 – amit
@herohuyongtao我知道找不到这个数组返回的最小数字,但是不知道如何解决这个问题 – user3219308