USACO: подмножества (неэффективные) - PullRequest
Новая
       10

USACO: подмножества (неэффективные)

0 голосов
/ 23 июня 2011

Я пытаюсь решить подмножества с учебного шлюза USACO ...

Постановка задачи

Для многих наборов последовательных целых чисел от 1 до N (1 <= N <= 39) можно разбить набор на два набора, суммы которых идентичны. </p>

Например, если N = 3, можно разделить множество {1, 2, 3} одним способом, чтобы суммы обоих подмножеств были идентичны:

{3} и {1,2} Это считается как одно разделение (то есть изменение порядка считается как одно и то же разделение и, следовательно, не увеличивает количество разделов).

Если N = 7, существует четыре способа разбить множество {1, 2, 3, ... 7} так, чтобы каждая секция имела одинаковую сумму:

{1,6,7} и {2,3,4,5} {2,5,7} и {1,3,4,6} {3,4,7} и {1,2,5,6} {1,2,4,7} и {3,5,6} Учитывая N, ваша программа должна вывести количество способов, которыми набор, содержащий целые числа от 1 до N, может быть разделен на два набора, суммы которых идентичны. Выведите 0, если таких способов нет.

Ваша программа должна рассчитать ответ, а не искать его из таблицы.

Конец

До того, как я запустил O (N * 2 ^ N), просто переставляя множество и находя суммы.

Узнав, насколько это ужасно неэффективно, я перешел к составлению карт последовательностей сумм ... http://en.wikipedia.org/wiki/Composition_(number_theory)

После многих проблем с кодированием, чтобы убрать повторы, все еще слишком медленно, поэтому я вернулся к исходной точке: (.

Теперь, когда я посмотрел более внимательно на проблему, похоже, что я должен попытаться найти способ не находить суммы, а на самом деле перейти непосредственно к количеству сумм с помощью некоторой формулы.

Если кто-нибудь может подсказать мне, как решить эту проблему, я весь в ушах. Я программирую на Java, C ++ и Python.

Ответы [ 2 ]

1 голос
/ 07 ноября 2013

На самом деле, есть лучшее и более простое решение.Вы должны использовать Динамическое программирование .В вашем коде у вас будет массив целых чисел (размер которого равен сумме), где каждое значение в индексе i представляет количество способов, которым возможно разделить числа так, чтобы один из разделов имел сумму я .Вот как ваш код может выглядеть в C ++: 

int values[N];
int dp[sum+1]; //sum is the sum of the consecutive integers

int solve(){
    if(sum%2==1)
        return 0;
    dp[0]=1;
    for(int i=0; i<N; i++){
        int val = values[i]; //values contains the consecutive integers
        for(int j=sum-val; j>=0; j--){
            dp[j+val]+=dp[j];
        }
    }
    return dp[sum/2]/2;
}

Это дает вам решение O (N ^ 3), которое достаточно быстро для этой проблемы.

У меня естьне тестировал этот код, поэтому может быть синтаксическая ошибка или что-то еще, но вы поняли.Дайте мне знать, если у вас есть еще вопросы.

0 голосов
/ 13 августа 2012

Это то же самое, что нахождение члена коэффициента x ^ 0 в полиноме (x ^ 1 + 1 / x) (x ^ 2 + 1 / x ^ 2) ... (x ^ n + 1 / x^ n), который должен занимать верхнюю границу O (n ^ 3).

...