Тема: Timus 1005
есть задача - http://acm.timus.ru/problem.aspx?space=1&num=1005
сдал ее перебором подмножеств, но слышал о более оптимальном решении динамикой.
кто-нибудь может рассказать подробнее, как? спасибо.
Re: Timus 1005
ну стандартный рюкзак правда он хуже по времени получается
Re: Timus 1005
А код можно увидеть где-нибудь? И почему хуже по времени?
Re: Timus 1005
int dm[70000];
void solve() {
int n;
scanf("%d", &n);
memset(dm, 0, sizeof(dm));
dm[0] = 1;
int s = 0;
for(int i = 0; i < n; ++i) {
int w;
scanf("%d", &w);
for(int j = 2000000; j >= 0; --j) {
if (dm[j / 30] & (1 << (j % 30)) && j + w <= 2000000) {
dm[(j + w) / 30] |= (1 << ((j + w) % 30));
}
}
s += w;
}
int res = 3000000;
for(int i = 0; i < 2000001; ++i) {
if ((dm[i / 30] & (1 << (i % 30))) == 0 ) continue;
res = min(res, abs(s - i - i));
}
printf("%d", res);
} ну перебор подмножест будет со сложностью O(2^n), динамика же O(n * M), где M максимальная сумма всех кучек
Re: Timus 1005
Думаю самое быстрое решение - разделить все камни пополам (в каждой не больше 10) в каждой из половинок перебрать все подмножества отсортировать и найти лучшую комбинацию ~ O(2^(N / 2) )