最小加法——算法

Question

我在网上遇到了这个问题。

给定一个整数：N和一个数组int arr[]，您必须向数组中添加一些元素，以便可以使用（添加）数组中的元素从1生成到N。

请记住，在生成某个x（1）时，只能使用数组中的每个元素一次

For example:

N=6, arr = [1, 3] 

1 is already in arr. 

add 2 to the arr. 

3 is already in arr 

4 = 1 + 3 

5 = 2 + 3 

6 = 1 + 2 + 3 

So we return 1 since we only need to add one element which is 2.

有人能给点提示吗？

Answer 1

一种方法是生成一组由数组生成的所有可能的数字。这可以在O（n^2）时间内完成。然后，在O（1）时间内检查集合中是否存在从1到n的数字。如果数字不存在，则将其添加到最初为零的最少添加数字的计数中，并创建一个新的空集。取上一个集合的所有元素，将不存在的数字添加到它们中，然后将它们（集合添加方法）添加到新集合中。用原始集和新集的并集替换原始集。从1到n进行此操作将在O（n^3）时间内给出最小加法数之和。

Answer 2

设A为输入数字的集合。

初始化布尔数组B以存储在B[i]中，无论我们是否可以通过在a中添加数字来“生成”i，如问题中所述。使所有B[i]最初为假。

然后，伪代码：

for i = 1 to N

     if B[i] && (not A.Contains(i))
        continue next i

      if not A.Contains(i)
        countAdded++

      for j = N-i downTo 1
        if B[j] then B[j+i] = TRUE

      B[i] = TRUE

    next i

解释：

在（主）循环（i）中：对于我们可以用A中小于i的值构造的值，B包含TRUE。因此，最初，当i=1时，所有B都是FALSE。

那么，对于每个i，我们有两个方面需要考虑：（a）B[i]已经是真的了吗？如果不是，我们将不得不添加i；（b） 我现在在吗？因为，看前面的评论，此时我们还没有处理那个A值。所以，即使B【i】已经为真，我们也必须为所有（其他）B标记真，我们可以用i来达到。

因此：

对于每个i，我们首先确定这两种情况是否适用，如果不适用，我们跳到下一个i。

然后，如果A不（还）包含i，则必须是B[i]为FALSE的情况，请参阅跳过条件，因此我们将添加i（概念上为A，但实际上没有必要将其放入A中）。

接下来，要么我们最初在A中加入了i，要么我们刚刚添加了它。在任何情况下，我们都需要为所有可以用这个新i构造的值标记B TRUE。为此，我们最好向下扫描现有的B；否则，我们可能会将i添加到“新”B值中，该B值已将i作为组成部分。

最后，B[i]本身被设置为TRUE（它可能已经是TRUE...），仅仅是因为i在A中（原始地，或通过添加）

Answer 3

除了N=2和N=1之外，总是可以通过将1的子集添加到N-1数字来生成N。因此，当数组中已经存在上一个到X-1的连续元素时，必须生成一个数字X。示例-

    arr[] = {1, 2, 5}, N = 9
    ans := 0
    1 is already present.
    2 is already present.
    3 is absent. But prior 1 to (3 - 1) elements are present. So 3 is added in the array. But as 3 is built using already existed elements, so answer won't increase.
    same rule for 4 and 5

    So, ans is 0

    arr[] = {3, 4}, for any N >= 2

    ans = 2

    arr[] = {1, 3}, for any N >= 2

    ans = 1

所以，看起来，如果数组中只有1和2不存在，我们必须添加该元素，而不管之前的元素是否已经在数组中。所有后面的数字都可以通过使用以前的元素来制作。并且当尝试制作任何数字X（

因此，基本上我们需要检查是否存在1和2。所以这个问题的答案不会大于2

在上述算法中，我们假设，当数组中不存在新元素X，但可以使用数组中已存在的元素生成新元素时，答案不会增加，但会在数组中添加X，以用于下一个数字生成。如果无法在数组中添加X，该怎么办？

然后，基本上它会变成一个子集和问题。对于每个缺失的数字，我们必须检查该数字是否可以使用数组中的任何元素子集来生成。这是典型的O（N^2）动态规划算法。

int subsetSum(vector<int>& arr, int N)
{
    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
    //  with sum equal to i
    bool subset[N + 1][arr.size() + 1];

    // If sum is 0, then answer is true
    for (int i = 0; i <= arr.size(); i++)
      subset[0][i] = true;

    // If sum is not 0 and set is empty, then answer is false
    for (int i = 1; i <= N; i++)
      subset[i][0] = false;

     // Fill the subset table in botton up manner
     for (int i = 1; i <= N; i++)
     {
       for (int j = 1; j <= arr.size(); j++)
       {
         subset[i][j] = subset[i][j - 1];
         if (i >= set[j - 1])
           subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
       }
     }

     unordered_map<int, bool> exist;
     for(int i = 0; i < arr.size(); ++i) {
         exist[arr[i]] = true;
     }

     int ans = 0;
     for(int i = 1; i <= N; ++i) {
          if(!exist[i] or !subset[i][arr.size()]) {
              ans++;
          }
     }

     return ans;
}