Оптимизация максимального значения в списке за время O (nlog (диапазон границ)) - PullRequest
Новая
       37

Оптимизация максимального значения в списке за время O (nlog (диапазон границ))

0 голосов
/ 10 октября 2018

В настоящее время у меня есть проблема, в которой у нас есть два массива, скажем x=[x1,x2,x3,...,xn] и массив y=[y1,y2,y3,...,yn] и значение, скажем, k.Теперь я должен сгенерировать массив скажем z=[z1,z2,z3,...,zn] из k, такой, что z1+z2+z3...+zn=k.Для разных сгенерированных z, что будет минимальным значением max [(x1-z1)*y1, (x2-z2)*y2, (x3-z3)*y3, ...., (xn-zn)*yn].т.е. минимальное значение максимум (x[i]-z[i])*y[i].Например, если x=[2,3,4,1,6] и y=[3,5,2,7,3] и k = 4, то взятие z=[0,1,0,0,3] дает массив [6,10,8,7,9], для которого максимум равен 10, что также является минимальным максимумом.
Я разработал алгоритм, который вычисляет его в O(nlog(n)+k). Вот если k будет очень большим, чем мой алгоритм будет неэффективным.Можем ли мы сделать это в O(n) или O(nlog(n)).Мой текущий алгоритм: 

1. l=[] //initialize empty array
2. for i from 0 to n:
     l.append(x[i]*y[i],y[i])
3. Sort l in decreasing order of (x[i]*y[i])
4. while(m>0):
     num=l[0][0]-l[1][0] //take difference of two largest x[i]*y[i]
     t=(num/l[0][1])+1 //Choose appropriate number to subtract to minimize 
                         the maximum
     t=max(0,t)        // t must not be negative
     l[0][0]=l[0][0]-t*l[0][1]
     Put l[0] at correct position in sorted list l //Since value of 
                                                     l[0][0] has 
                                                     changed we will 
                                                     place it at 
                                                     correct position 
                                                     in already sorted  
                                                     l (using binary 
                                                     search)
     m=m-t
5.Print l[0][0] as the minimum maximum

1 Ответ

0 голосов
/ 10 октября 2018

Если вы можете рассчитать или оценить нижнюю и верхнюю границы вашего ответа (что является минимально возможным максимальным значением вашего результирующего массива), то вы можете использовать двоичный поиск для решения этой проблемы.

Для двоичного поискаответ, теперь нам нужен предикат, назовем его p.

p(val) = true, если существует массив z такой, что максимальное значение (xi-zi) * yi меньше, чем равно valи false в противном случае

Чтобы доказать, что бинарный поиск будет работать с использованием этого предиката, нам нужно доказать две вещи:

  1. , если p(a) = true, то p(b) = true для всех b >= a
  2. если p(a) = false, то p(b) = false для всех b <= a

Эти два утверждения могут быть доказаны с использованием определения предиката.

Для оценкиПредикат для данного значения, попробуйте оценить каждый zi:

  1. , если xi * yi > val, затем выберите минимально возможное zi, такое, что xi*yi - zi*yi <= val
  2. , в противном случае выберите максимально возможное(по величине) zi так, что xi*yi - zi*yi <= val все еще верно

Теперь будет три случая:

  1. , если сумма zi равна <k, то вы можете выбрать любой положительный zi и увеличить его до точкиэта сумма zi становится k.Вы можете видеть, что увеличение этого zi не повлияет на предикатное значение, так как максимум (xi-zi)*yi все равно будет меньше, чем k.В этом случае предикат будет истинным.
  2. , если сумма точно равна k, то снова истина.
  3. , если сумма больше k, тогда результат ложен.Как и в этом случае, нельзя выбрать отрицательный zi и уменьшить его еще больше, поскольку он уже имеет максимально допустимое значение.

Теперь пришло время для некоторого кода. 

low = -100
high = 100 # these two are assumed values

x = [2, 3, 7, 1, 6]
y = [3, 5, 2, 7, 3]
k = 4

def p(val):
    sum_zi = 0  # sum of possible zi
    for idx in range(len(x)):
        if x[idx]*y[idx] > val:
            diff = x[idx]*y[idx] - val
            zi = (diff + y[idx] - 1) // y[idx]
            sum_zi += zi
        else:
            diff = x[idx]*y[idx] - val
            zi = diff // y[idx]
            sum_zi += zi
    return sum_zi <= k

while low < high:
    mid = (low + high)//2
    if p(mid):
        high = mid
    else:
        low = mid+1

print("Min possible max value", low)
# output = 10

Используя это, вы можете вычислить свой результат в nlog(range of bounds)

...