Задать вопрос

Ашот Такиев

Лайки

  • Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Задача о рюкзаке, даже о двух :)
    Заводите массив M[0..S/3,0..S/3] (можно битовый, но лучше побольше - чтобы хранить обратные ссылки). В нём будут отмечены элементы M[a,b], такие, что из уже просмотренных элементов текущего набора можно выбрать непересекающиеся подмножества с суммами a и b.
    Когда приходит очередной элемент x - выполняете M[a,b]=M[a,b] | M[a-x,b] | M[a,b-x] для всех a,b начиная с конца (с больших a,b). Если при этом 0 сменился на 1 - помечаете в массиве обратных ссылок, из какого элемента вы сюда попали.
    Сложность - O(n*S^2). Можно ли сделать лучше, не знаю.

    Вот вариант кода - но он печатает только два множества. Как напечатать третье, разберётесь.
    spoiler
    static void Main(string[] args) {
            int[] dat=Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
            int S=0;
            foreach(int x in dat) S+=x;
            if(S%3!=0) {
                Console.WriteLine("-1"); return;
            }
            S/=3;
            int[,] M=new int[S+1,S+1];
            M[0,0]=-1;
            foreach(int x in dat) {
                for(int a=S;a>=0;a--) {
                    for(int b=S;b>=0;b--) {
                        if(M[a,b]==0) {
                            if(a>=x && M[a-x,b]!=0) M[a,b]=x;  // back by set1
                            else if(b>=x && M[a,b-x]!=0) M[a,b]=-x;  // back by set2
                        }
                    }
                }
            }
            if(M[S,S]==0) {
                Console.WriteLine("-1"); return;
            }
            int u=S,v=S;
            string res1="",res2="";
            while(u!=0 || v!=0) {
                if(M[u,v]>0) {
                    res1+=" "+M[u,v]; u-=M[u,v];
                } else {
                    res2+=" "+(-M[u,v]); v+=M[u,v];
                }
            }
            Console.WriteLine(res1);
            Console.WriteLine(res2);
        }

    Ответ написан
    10 комментариев
    10 комментариев

  • Что не так с алгоритмом для поиска наибольшей неубывающей подпоследовательности?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В этой задаче нельзя обойтись "текущей подпоследовательностью". Надо держать самые длинные подпоследовательности, заканчивающиеся на разные элементы (чем больше элемент, тем длиннее должна быть подпоследовательность, заканчивающаяся на него), и когда приходит новый элемент, то присоединить его к самой длинной из последовательностей, к какой возможно (причём старую последовательность сразу выбрасывать нельзя - она ещё может пригодиться), а потом выбросить неоптимальные (последовательность такой же длины, что и другая, но заканчивающаяся на больший элемент).
    Например, для последовательности [1,2,7,8,9,5,6,3] вам придётся помнить
    [1,2,7,8,9]
    [1,2,5,6]
    [1,2,3]
    [1,2]
    [1]
    Любая из этих последовательностей может быть началом правильного ответа.
    Так что начало решения у вас правильное. Но в векторе d должны храниться не числа, а их индексы (и поиск должен быть более сложным), а массив prev надо модифицировать так: prev[i]=d[j-1].
    Для примера [1,2,7,8,9,5,6,3] получаем
    d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
    (значение -1 используется для обозначения ситуации "нет такого индекса").
    Ответ написан
    3 комментария
    3 комментария