这不能从一组中获得的最低金额 [英] Minimum sum that cant be obtained from a set

问题描述

由于正整数，它的元素不需要是不同的，我需要找到最小的是不能从给定的任何一个子集来获得非负和的集合S。

例如：如果S = {1，1，3，7} ，我们可以得到 0 为（S'= {}）， 1 为（S'= {1}）， 2 为（S'= {1,1}）， 3 为（S'= {3}）， 4 为（S'= {1,3}）， 5 为（S'= {1， 1，3}），但我们不能 6 。

现在我们得到一个数组A ，由 N 正整数。他们是 M 查询，分别由两个整数丽和日描述第i个查询：我们需要找到这笔款项是不能从阵列中获得元素= {A [李]，A [李+ 1]，...，A [RI-1 ]，A [日]} 。

我知道用蛮力的方法来找到它的O（2 ^ n）的工作要做。但考虑到 1≤N，M≤100,000 。这不能做。 那么，他们做任何有效的办法。

解决方案

概念

假设我们具有布尔数组重新presenting到目前为止还没有发现哪个号码（通过累加的方式）。

对于每个编号 N 我们遇到的订购（增加值）的S子集，我们做到以下几点：

在号
1. 对于每个现有的真值在位置我 ，我们设置号码[I + N] 到真
2. 我们设置号码[N] 到真

通过这种筛子，我们将标志着所有的发现的编号为真，并通过数组迭代时，算法结束会找到我们的最低用不上总和。

---

细化

显然，我们不能有这样的解决方案，因为该数组必须是无限的，以工作为数字的所有集合。

这个概念可以通过以下几点意见加以改进。随着输入 1，1，3 ，阵列变成（按顺序）：

^{（数字重新present 真值）}

这是重要的观察可以做：

• （3）对于每下一个数字，如果已经找到了previous数字将被添加到所有这些数字。这意味着如果没有间隙的号码前，将有后，这个数字已经被处理无缝隙

有关下一输入 7 我们可以断言：

• （4）由于输入集是有序的，将有比没有数量少 7
• （5）如果有超过 7 无数量少，则 6 不能获得

我们可以得出一个结论，即：

• （6）的第一个缺口再presents最低用不上的数

---

算法

由于（3）和（6），我们并不真正需要的数字阵，我们只需要一个值，最大为重present迄今为止发现的最大数量

这样，如果在未来数 N 大于 MAX + 1 ，那么差距将是制作和 MAX + 1 是最小用不上的数量。

另外，最高变成最大+ N 。如果我们通过运行整个取值，其结果是 MAX + 1 。

实际code（C＃，方便地转换为C）：

 静态INT计算（INT [] S）
{
    INT最大= 0;
    的for（int i = 0; I＆LT; S.Length;我++）
    {
        如果（S [1]  - ; = MAX + 1）
            最大= MAX + S [I]
        其他
            返回MAX + 1;
    }
    返回MAX + 1;
}
 

应该运行pretty的快，因为它是明显的线性时间（为O（n））。由于输入到该函数应该进行排序，以快速排序，这将变成为O（nlogn）。我已经成功地得到结果 M = N = 100000 8芯在不到5分钟。

使用的10 ^ 9，数字上限一个基数排序可以用于近似为O（n）的时间排序，但是这仍然是由于需要各种巨量方式超过2秒。

但是的下，我们可以使用1 统计概率正在randomed ，以消除子集的在的排序。在开始时，检查是否存在1中取值，如果没有的话，因为它不能获得每个查询的结果为1。

据统计，如果我们随机从10 ^ 9号10 ^ 5次，我们还没有得到一个1 99.9％的机会。

在每个排序，检查该子集包含1，如果没有，那么它的结果为1。

通过这种修改，在code运行在2毫秒我的机器上。下面是关于 http://pastebin.com/rF6VddTx

这code

Given a set S of positive integers whose elements need not to be distinct i need to find minimal non-negative sum that cant be obtained from any subset of the given set.

Example : if S = {1, 1, 3, 7}, we can get 0 as (S' = {}), 1 as (S' = {1}), 2 as (S' = {1, 1}), 3 as (S' = {3}), 4 as (S' = {1, 3}), 5 as (S' = {1, 1, 3}), but we can't get 6.

Now we are given one array A, consisting of N positive integers. Their are M queries,each consist of two integers Li and Ri describe i'th query: we need to find this Sum that cant be obtained from array elements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]} .

I know to find it by a brute force approach to be done in O(2^n). But given 1 ≤ N, M ≤ 100,000.This cant be done . So is their any effective approach to do it.

解决方案

Concept

Suppose we had an array of bool representing which numbers so far haven't been found (by way of summing).

For each number n we encounter in the ordered (increasing values) subset of S, we do the following:

1. For each existing True value at position i in numbers, we set numbers[i + n] to True
2. We set numbers[n] to True

With this sort of a sieve, we would mark all the found numbers as True, and iterating through the array when the algorithm finishes would find us the minimum unobtainable sum.

---

Refinement

Obviously, we can't have a solution like this because the array would have to be infinite in order to work for all sets of numbers.

The concept could be improved by making a few observations. With an input of 1, 1, 3, the array becomes (in sequence):

^{(numbers represent true values)}

An important observation can be made:

• (3) For each next number, if the previous numbers had already been found it will be added to all those numbers. This implies that if there were no gaps before a number, there will be no gaps after that number has been processed.

For the next input of 7 we can assert that:

• (4) Since the input set is ordered, there will be no number less than 7
• (5) If there is no number less than 7, then 6 cannot be obtained

We can come to a conclusion that:

• (6) the first gap represents the minimum unobtainable number.

---

Algorithm

Because of (3) and (6), we don't actually need the numbers array, we only need a single value, max to represent the maximum number found so far.

This way, if the next number n is greater than max + 1, then a gap would have been made, and max + 1 is the minimum unobtainable number.

Otherwise, max becomes max + n. If we've run through the entire S, the result is max + 1.

Actual code (C#, easily converted to C):

static int Calculate(int[] S)
{
    int max = 0;
    for (int i = 0; i < S.Length; i++)
    {
        if (S[i] <= max + 1)
            max = max + S[i];
        else
            return max + 1;
    }
    return max + 1;
}

Should run pretty fast, since it's obviously linear time (O(n)). Since the input to the function should be sorted, with quicksort this would become O(nlogn). I've managed to get results M = N = 100000 on 8 cores in just under 5 minutes.

With numbers upper limit of 10^9, a radix sort could be used to approximate O(n) time for the sorting, however this would still be way over 2 seconds because of the sheer amount of sorts required.

But, we can use statistical probability of 1 being randomed to eliminate subsets before sorting. On the start, check if 1 exists in S, if not then every query's result is 1 because it cannot be obtained.

Statistically, if we random from 10^9 numbers 10^5 times, we have 99.9% chance of not getting a single 1.

Before each sort, check if that subset contains 1, if not then its result is one.

With this modification, the code runs in 2 miliseconds on my machine. Here's that code on http://pastebin.com/rF6VddTx

这篇关于这不能从一组中获得的最低金额的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！