Алгоритм: взвешенные суммы при вращении
Извините, я надеюсь, что это не слишком далеко от темы для stackru. У меня есть алгоритм, который я хотел бы доказать, правильно, или найти контрпример, если это не так.
Здесь проблема. У меня есть набор строго положительных весов: w1, w2, w3, ... wn.
У меня есть вектор логических значений длины m, где m>n. Вектор должен иметь ровно n истинных значений и mn ложных значений.
Например, если m=5 и n=3, то v может быть (1, 1, 0, 1, 0)
Далее у нас есть функция, которая отображает v-векторы на натуральные числа:
int f(vector v) {
sum=0, wIndex=1, pow=1;
// v must have exactly n ones
for(int index=0;index<m;index++) {
if(v[index]==1)
sum=sum + w[wIndex++]*pow;
pow=pow*2;
}
return sum;
}
где w[wIndex] дает веса, w1, w2, w3 ... wn.
EXAMPLE:
suppose v=(0, 1, 1, 0, 1) and w1=3, w2=4, w3=6
f(v) would be 3*2 + 4*4 + 6*16 = 118.
Далее Рассмотрим круговые повороты v, например, если v=(0, 1, 1, 0, 1), то rotate(v, 3) поворачивается на v на 3 позиции влево или (0, 1, 0, 1, 1). Круговые вращения сохраняют m (длина) и n (количество единиц).
Мы определяем minF(v) как минимальное значение f для всех возможных круговых вращений v. Это может быть реализовано следующим образом:
int minF(vector v) {
int min=f(v);
for(int amount=1; amount<m; amount++) {
if(f(rotate(v, amount))<min)
min=f(rotate(v, amount));
}
return min;
}
где rotate(v, k) вращает v по кругу на k мест
EXAMPLE:
suppose v=(0, 1, 1, 0, 1) and all weights are 3
The rotation that has the minimum f is v=(1, 1, 0, 1, 0),
Thus minF(v)=3 + 6 + 24 = 33
И вот наконец мы добрались до вопроса:
Доказательство или опровержение оптимума (m, n) дает вектор, такой что minF (оптимум (m, n)) >= minF(w) для всех возможных векторов w длины m с n единицами, где оптимум определяется следующим образом:
vector optimum(int m, int n) {
vector opt=new vector[m];
int ones=n, zeros=m-n, balance=0;
for(int index=0; index<m; index++)
if(balance<ones) {
opt[index]=1;
balance=balance + zeros;
}
else {
opt[index]=0;
balance=balance - ones;
}
}
return opt;
}
Наконец, вот несколько примеров оптимальных прогонов:
optimum(10, 1) --> 1000000000
optimum(10, 2) --> 1000010000
optimum(10, 3) --> 1001001000
optimum(10, 4) --> 1010010100
optimum(10, 5) --> 1010101010
optimum(10, 6) --> 1101011010
optimum(10, 7) --> 1110110110
optimum(10, 8) --> 1111011110
optimum(10, 9) --> 1111111110
Оптимум, по сути, распространяет их как можно дальше друг от друга.
Я сделал много эмпирических тестов, и этот алгоритм, кажется, всегда работает, но мне действительно нужно доказательство того, что это правильно.
PS Если вы решите это, я куплю вам пиццу.
1 ответ
Я нашел это неожиданно интересным... Это то, что я получил примерно через 2 часа вчера. Это еще не доказательство, но это основа для рассуждений - прямо сейчас его достаточно для доказательства с небольшим массажем, где n=2, и я думаю, что я могу построить его до n > 2, но еще не совсем там. Увы, у меня есть дневная работа, поэтому я должен немного ее уложить.
Надеюсь, это поможет - извините, если это не так.
Веса не могут вращаться. Максимальный шаблон для m=9, n=3 всегда равен 000000111, минимальный шаблон всегда 111000000. Обобщение этого тривиально.
Кондера m=6, n=2 и посмотрите на таблицу. w1_k означает, что местоположение w1 является смещением k.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- 000011 000101 001001 010001 100001
w2_4 -- -- 000110 001010 010010 100010
w2_3 -- -- -- 001100 010100 100100
w2_2 -- -- -- -- 011000 101000
w2_1 -- -- -- -- -- 110000
w2_0 -- -- -- -- -- --
Поскольку значение w1 является постоянным, мы можем сделать простой вывод о том, что оно строго увеличивается с ростом w1.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- 000011 > 000101 > 001001 > 010001 > 100001
w2_4 -- -- 000110 > 001010 > 010010 > 100010
w2_3 -- -- -- 001100 > 010100 > 100100
w2_2 -- -- -- -- 011000 > 101000
w2_1 -- -- -- -- -- 110000
w2_0 -- -- -- -- -- --
И такой же вывод про колонку и w2.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- 000011 > 000101 > 001001 > 010001 > 100001
V V V V
w2_4 -- -- 000110 > 001010 > 010010 > 100010
V V V
w2_3 -- -- -- 001100 > 010100 > 100100
V V
w2_2 -- -- -- -- 011000 > 101000
V
w2_1 -- -- -- -- -- 110000
w2_0 -- -- -- -- -- --
Мы видим, что кольца соответствуют диагоналям. Этот пример имеет три разных кольца. Я отмечен (), [], {}.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- [000011]>(000101)>{001001}>(010001)>[100001]
V V V V
w2_4 -- -- [000110]>(001010)>{010010}>(100010)
V V V
w2_3 -- -- -- [001100]>(010100)>{100100} <- minF(100100)
V V
w2_2 -- -- -- -- [011000]>(101000) <- minF(010100)
V
w2_1 -- -- -- -- -- [110000] <- minF(000011)
w2_0 -- -- -- -- -- --
Что общего у колец? Это расстояние между пробелами 1.
[] = {All sets with 4 continuos 0's and an adject one}
= { 100001, 000011, 000110, 001100, 011000, 110000 }
= ((0,4))
() = {All sets with 3 continuos 0's and one single 0}
= { 000101, 001010, 001010, 010100, 101000, 010001, 100010 }
= ((1,3))
{} = {All sets with 2 strings of 2 0's.}
= { 100100, 010010, 001001 }
= ((2,2))
Я назову ((g_1,g_2)) разрыв, установленный для кольца, который описывает промежутки между строками. Кольцо, описанное {}, является самым центральным кольцом. При длине струны странного размера центральное кольцо имеет ширину 1. при четной длине струны центральное кольцо имеет ширину 2.
w1_6, w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_6 -- [0000011]>(0000101)>{0001001}>{0010001}>(0100001)>[1000001]
V V V V V
w2_5 -- -- [0000110]>(0001010)>{0010010}>{0100010}>(1000010)
V V V V
w2_4 -- -- -- [0001100]>(0010100)>{0100100}>{1000100}
V V V
w2_3 -- -- -- -- [0011000]>(0101000)>{1001000}
V V
w2_2 -- -- -- -- -- [0110000]>(1010000)
V
w2_1 -- -- -- -- -- -- [1100000]
w2_0 -- -- -- -- -- -- --
{} = ((3,2))
() = ((4,1))
[] = ((5,0))
Из заданного зазора можно сделать вывод, что расстояние от центральной линии равно расстоянию между двумя индикаторами зазора, деленному на 2, до следующего наибольшего значения int.
dist_from_center( ((2,2)) ) = ceil(| 2 - 2 | * .5 ) = 0
dist_from_center( ((3,1)) ) = ceil(| 3 - 1 | * .5 ) = 1
dist_from_center( ((4,0)) ) = ceil(| 4 - 0 | * .5 ) = 2
dist_from_center( ((3,2)) ) = ceil(| 3 - 2 | * .5 ) = 1
dist_from_center( ((4,1)) ) = ceil(| 4 - 1 | * .5 ) = 2
dist_from_center( ((5,0)) ) = ceil(| 5 - 0 | * .5 ) = 3
Итак, затем возвращаем его обратно, тогда, если dist между элементами в gap_set a больше, чем dist в gap_set b, тогда должен быть элемент в множестве gap, который меньше, чем какой-либо элемент в множестве b промежутка.
dist_from_center( ((a_1,a_2)) ) > dist_from_center( ((b_1,b_2)) )
==Implies==> minF( ((a_1, a_2)) ) < minF( ((b_1, b_2)) )
Что поддерживает вас в этом, что расширение 1 как можно больше приводит к максимальному minF для набора строк.