修改子集合

给定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。 所以这里回答是“不”。

来源

2014-01-25 user3219308

你需要提供你所尝试过的。 – herohuyongtao

@harold No. {1,2,3}是一个反例。 – amit

@herohuyongtao我知道找不到这个数组返回的最小数字，但是不知道如何解决这个问题 – user3219308

我知道发现不能用这个数组返回的最小数目，但不知道如何解决这个问题

第一，请问该数组只有一个元素？如果是这样，答案是肯定的。

否则，找到最小不可能的总和。它比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。这就是算法的作用。

来源

2014-01-25 09:42:53 user2357112

可否请您提供一个有效的算法，因为根据我的算法，我将检查从一个开始的每个数字，对于大型的N – user3219308

@ user3219308来说效率太低：那么，找到最低不可能总和的算法相当低效。我将用一种应该能够快速解决这两个问题的算法进行编辑。 – user2357112

还有一个问题，最小数目可能小于L.但是，我99.9％相信，如果1不在数组中，并且数组包含多于1个元素 - 则无法获得全部总和。（这个声明需要证明！）。然而，这个解决方案在arr = [5]中失败了，例如，无法实现的最小元素是1，答案仍然是'是'。 – amit

首先对数组中的所有元素进行排序。如果你想从数组的元素中得到L和S之间的所有值，那么L = 1并且元素应该是2^i的形式。最大的元素可能不是形式2^i，因为总和不必是形式（2^i - 1）。

来源

2014-01-25 09:45:44

查看阿米特的反例。 – user2357112

@ user2357112：谢谢指出。现在我纠正了算法。最伟大的元素可能不是形式2^i。 –

仍然错误。 “{1,1,1}”是我认为你想说的一个反例。 – user2357112

回答

相关问题