algorithm - 最少加法--算法

Question

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

Given an integer:N and an array int arr[], you have to add some elements to the array so that you can generate from 1 to N by using (add) the element in the array.

请记住，在生成某个 x (1<=x<=N) 时，您只能使用数组中的每个元素一次。返回最少相加数的个数。

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

N 始终可以通过将 1 的子集添加到 N - 1 数字(N = 2 除外)和 N = 1。因此，当数组中已经存在前一个 1 到 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 (> 2) 时，我们已经在数组中找到了之前的 1 到 X - 1 元素。所以 X 总是可以生成的。

所以，基本上我们需要检查 1 和 2 是否存在。所以这个问题的答案不会大于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;
}