Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Нахождение двух минимальных сумм чисел

Автор: S_lip 25.12.2007 18:23

Здравствуйте!
Вот такая задачка:

Дана упорядоченная последовательность N чисел. (2<=N<=200). Каждое число больше 0, но меньше 30000. Нужно из этого ряда найти два набора чисел, величины которых должны быть равны и минимальны. Гарантируется, что эта величина будет меньше 100000. Эту величину нужно выписать.

Примеры:
Дано: 1 2 3 4 5. Группы чисел: 1 2 и 3. Ответ: 3.
Дано: 1 2 5 5 8 10 102. Группы чисел: 5 и 5. Ответ: 5.
Дано: 2 3 4 5. Группы чисел: 2 3 и 5. Ответ: 5.
Дано: 1 3 5 7 13 21. Группы чисел: 1 7 и 3 5. Ответ: 8.
Дано: 1 2 5 8 14. Группы чисел: 1 2 5 и 8. Ответ: 8.


Вот я придумал вот такое решение:
http://img401.imageshack.us/img401/500/20308125la9.png

const
MaxCount=200;
MaxSum=100000;
type
pair=record
l,r:longint;
end;
var
a:array [1..MaxCount] of integer;
b:array [0..50000] of pair; //чтоб хватило
f:text;
n,i,j,k,d:integer;
begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do readln(f,a[i]);
close(f);

d:=0;
repeat
inc(d);
b[0].l:=a[d];
b[0].r:=0;
i:=1;
k:=d;

repeat
inc(k);
for j:= 0 to (i-1) do begin
b[j+i].l:=b[j].l;
b[j+i].r:=b[j].r+a[k];
inc(b[j].l , a[k]);
end;
j:=1;
inc(i,i);
while (j<=i) and (b[j-1].l<>b[j-1].r) do inc(j);
until(j<=i) or (b[0].l>MaxSum)

until j<=i;

writeln(b[j-1].l);
end.


Программа перебирает все возможне пары сначало с участием первого числа. Если сумма этих пар больше 100000, а равные величины так и не найдены, то перебирает все возможные пары с участием второго числа и т.д.

Это решение кушает очень много памяти и при большом N вылетает. Возможно, есть более элегантное и правильное решение? =)

Автор: Michael_Rybak 25.12.2007 18:51

Любые решения этой задачи будут эвристическими, поскольку она NP-полная.

Автор: andriano 25.12.2007 20:48

Непонятно условие:
- что такое набор чисел?
- почему сначала о величинах говорится во множественном числе, а потом фигурирует "эта величина", которая, кстати, может достигать 100000, тогда как числа ограничены 30000?
- чем группа числе отличается он "не группы"? Как определить границы группы?

Автор: S_lip 25.12.2007 21:51

andriano, ок. постараюсь по подробней.
В файле "file.in" в первой строке написано число N (2<=N<=200).
Затем идет N строк, в каждой из которых написано число, величина которого больше одного, но меньше 30000.

Код
5
1
2
5
8
14


Набор чисел - это совокупность любых выбранных чисел (1 8 или 2 8 14 или 2 и т.д). Сложение всех чисел выбранного набора - сумма (или величина) (1+8=9, 2+8+14=24, 2=2).
"Эта величина" = Каждая из величин (сорри, что непонятно написал) = сумма чисел в одном и во втором наборе.

Если в "file.in" даны 100 чисел: от 29901 до 30000, то в каждом наборе будет максимум 3 числа, т.к. если будет 4, то их сумма будет больше 100000. У этой задачи будет ответ 59805 (29901+29904=29902+29903).

Группа чисел = набор чисел (опять, сорри за неточность)

Автор: andriano 26.12.2007 22:41

Понятно.
Просто уже неоднократно сталкивался с тем, что название темы никак не связано с ее содержанием, а слова "сумма" в теле темы нет.

Честно говоря не имею опыта в подобных оценках, но у меня складывается впечатление, что эта задача скорее олимпиадная, чем учебная. Поэтому, извини, вопрос: откуда она появилась?

Автор: S_lip 27.12.2007 4:10

andriano, нет это ты меня извини, что задачу описал не информативно.
Задача взята с латвийского портала по олимпиадным http://www.lio.lv/olimps/uzdevumi.php?show=3.
Если она очень мешает в ветке задач, то я могу поместить в тему "олимпиадные задачи".

Сорри, если что не так.

Автор: andriano 27.12.2007 13:07

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

В твоем решении не разбирался, но мне непонятно две вещи:
1. Почему именно пары? Ведь в условии, если я правильно его понял, возможны группы из произвольного количества элементов.
2. Зачем хранить пары? Это явно нерациональное использование памяти. У нас ведь переборная задача. Увеличение объема вычислений в 2-3 раза совершенно некритично. Поэтому не грех вычислять суммы прямо внутри цикла, нигде их не храня. Сохранять имеет смысл только наилучший из найденных ваиантов.


Через некоторое время.

Пожалуй, эвристики или, по крайней мере, некоторые из них лучше использовать ДО перебора. В частности, они могут помочь найти решение, не являющееся минимальным, но существенно сокращающее объем дальнейшего поиска.

И так же по поводу эвристик:
Какой именно из двух ваиантов тебе нужен?
1. Программа ВСЕГДА находит нужное решение. Сама программа при этом наиболее проста, но работать может до конца существования Вселенной (ну или, по крайней мере, до физического износа компа).
2. Программа, время работы которой ограничено. При этом она может выдать не то решение, которое нужно (т.е. не минимальное) или же совсем ничего не найти.

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

Автор: klem4 28.12.2007 1:26

в общем вот грубый перебор smile.gif Все приведенные тобой тесты программа прошла, на 200 чисел конечно такое решение врятли потянет, не пробовал, но думаю задумается прога надолго smile.gif

{$R-}

uses crt;

type
PTArray = ^TArray;
TArray = array [1..1] of Integer;

PTFlags = ^TFlags;
TFlags = array [1..1] of 0..1;
TIdxSet = Set of Byte;

const
MIN_SUM: Integer = 10001;
group1: TIdxSet = [];
group2: TIdxSet = [];

var
arr: PTArray;
size: Byte;
flags1, flags2: PTFlags;


procedure shift_flags(var flags: PTFlags);
var
i: Byte;
begin
i := size + 1;

repeat
dec(i);
inc(flags^[i]);
if flags^[i] = 2 then
flags^[i] := 0;
until flags^[i] = 1;
end;

procedure print_flags(const flags: PTFlags);
var
i: Byte;
begin
writeln;
for i := 1 to size do write(flags^[i]);
writeln;
end;

function group_sum(const flags: PTFlags): Integer;
var
i: Byte;
_result: Integer;
begin
_result := 0;

for i := 1 to size do
if flags^[i] = 1 then
_result := _result + arr^[i];

group_sum := _result;
end;

procedure copy_flags(const _from: PTFlags; var _to: PTFlags);
begin
move(_from^, _to^, size);
end;

function unique_flags(const a, b: PTFlags): Boolean;
var
i: Byte;
begin
i := size;

while (i > 0) and not (a^[i] * b^[i] = 1) do
dec(i);

unique_flags := (i = 0);
end;

procedure flags2set(const flags: PTFlags; var idx_set: TIdxSet);
var
i: Byte;
begin
idx_set := [];

for i := 1 to size do
if flags^[i] = 1 then
include(idx_set, i);
end;

function final_query(const flags: PTFlags): Boolean;
var
i: Byte;
begin
i := 1;

while (i <= size) and (flags^[i] = 1) do
inc(i);

final_query := (i > size);
end;

procedure get_solve;
var
s1, s2: Integer;
find: Boolean;
begin
repeat
shift_flags(flags1);

s1 := group_sum(flags1);

if (s1 < MIN_SUM) then begin
copy_flags(flags1, flags2);

find := false;

repeat
shift_flags(flags2);

if unique_flags(flags1, flags2) then begin

s2 := group_sum(flags2);

if s1 = s2 then begin

MIN_SUM := s1;

flags2set(flags1, group1);
flags2set(flags2, group2);

find := true;

end;
end;
until find or final_query(flags2);
end;

until final_query(flags1);
end;

var
f: Text;
i: Byte;

begin
clrscr;

assign(f, 'C:\input.txt');
reset(f);

readln(f, size);

getmem(arr, size * sizeof(TArray));

for i := 1 to size do begin
readln(f, arr^[i]);
write(arr^[i]:4);
end;

writeln;

close(f);

getmem(flags1, size * sizeof(TFlags));
getmem(flags2, size * sizeof(TFlags));

fillchar(flags1^, size * sizeof(TFlags), 0);

copy_flags(flags1, flags2);

get_solve;

freemem(flags1, size * sizeof(TFlags));
freemem(flags2, size * sizeof(TFlags));

writeln;

write('group1: ');

for i := 1 to size do
if i in group1 then write(arr^[i]:3, ',');

writeln;

write('group2: ');
for i := 1 to size do
if i in group2 then write(arr^[i]:3, ',');

writeln;
writeln;
writeln('S = ', MIN_SUM);

freemem(arr, size * sizeof(TArray));

readln;
end.

Автор: S_lip 29.12.2007 3:26

Спасибо всем большое за ответы!
klem4, спасибо за код.
Я "вроде бы" нашел решение.

Чтобы было более понятнее вот текст задачки:

Код
Давным-давно в высоких горах жил хмельной садовод Чек. У него было два сына Ричибук и Чибирук. Благодаря выращиванию хмеля Чек заработал достаточно большую стопку национальных денег -  фугриков. Особенность фугриков в том, что они могут иметь различные номиналы от 1 до 30000. Прошло время, дети стали взрослыми и хотели отправиться искать новые рассады хмеля. Однако, перед отправкой они зашли к отцу и попросить у него денег. Отец жалобно вздохнул и понял, что этого ему не избежать. Но лучше отдать по возможности меньше. Он также понял, что у детей должно быть по равной сумме денег, чтобы никто не обиделся.

В первой строке входного файла дано количество фугриков N (2<=N<=200). В каждой следующей строчке содержится число Ai, которое является i-той денежной единицей (1<=Ai<=30000).  Числа идут в возрастающем порядке.
Нужно найти и выписать сумму денег, которую Чеку придется отдать каждому из сыновей.
Гарантируется что всего Чек отдаст не более 100000 фугриков.

Автор: Ģirts Folkmanis (www.lio.lv/olimps)  - эт, чтоб меня не засудили =P


Цифры там немного другие, но это нисколько не меняет суть.
Чтобы не нагружать прогу сортировкой, данные уже отсортированы.

Вот мое решение:
const
MaxCount=200;
MaxSum=100000;
var
a:array [1..MaxCount] of integer;
u,d:array [1..(MaxSum div 2)*3+1] of longint; //"*3+1" для крайности, т.к. мы сначала заполняем, а потом отсеиваем ненужное
udn:longint;
b:array [0..(MaxSum div 2)] of longint; //если будет болше 50000, то общая сумма будет больше 100000
f:text;
n:byte;
i,j,k:longint;

begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do
readln(f,a[i]);
close(f);

for i:= 0 to (MaxSum div 2) do b[i]:=0;
udn:=1;
i:=1;
u[1]:=0;
d[1]:=a[1];
b[a[1]]:=a[1];

repeat
inc(i);

inc(udn);
u[udn]:=0;
d[udn]:=a[i];

for j:= 1 to udn-1 do begin
inc(udn);
u[udn]:=u[j];
d[udn]:=d[j]+a[i];
inc(udn);
if u[j]+a[i]<d[j] then begin
u[udn]:=u[j]+a[i];
d[udn]:=d[j];
end else begin
u[udn]:=d[j];
d[udn]:=u[j]+a[i];
end;
end;

inc(j);
repeat
k:=d[j]-u[j];
if (d[j]>(MaxSum div 2)) or (u[j]>(MaxSum div 2)) then begin
u[j]:=u[udn];
d[j]:=d[udn];
dec(udn);
end else if b[k]>0 then begin
if u[j]<u[b[k]] then begin
u[b[k]]:=u[j];
d[b[k]]:=d[j];
end;
u[j]:=u[udn];
d[j]:=d[udn];
dec(udn);
end else begin
b[k]:=j;
inc(j);
end;
until j>udn;
until b[0]>0;

writeln(u[b[0]]); //ответ
end.


По моим подсчетам, максимальное количество чисел, которые нужно будет перебирать, будет 16, а не 10, как говори andriano. Это числа 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 и еще одно до 30000. Почему эти числа? Потому, что из 1 2 можно максимум составить 3; из 1 2 4 - 7; 1 2 4 8 - 15 и т.д.

"Вроде бы" решил потому, что в тестере (на сайте с условием), этот код не прошел все тесты и в одном дал неправильный ответ. К тестам доступа нет. Может кто-нибудь может найти такие входные данный (основываясь на условие), чтобы эта программа дала неправильный ответ?

Автор: andriano 29.12.2007 3:38

Не мог бы ты объяснить, почему надо перебирать именно эти числа? Во входном файле может не оказаться ни одного из них.

Автор: S_lip 29.12.2007 4:24

Именно эти - чтоб получилась цепочка максимальной длины.
Можно, конечно, выбрать и этот ряд 1 3 5 10 20 40 80 160 320 640 1280 2560 5120 10240 20480 и еще одно до 30000. Можно и другой, но с учетом, чтобы числа были как можно меньше. Будут числа более большие - меньше шансов что следующее число будет меньше 30000 и, как следствие, длиннее цепь.

Автор: andriano 29.12.2007 16:10

Не понял.
Прочитав эту фразу:

Цитата
По моим подсчетам, максимальное количество чисел, которые нужно будет перебирать, будет 16, а не 10, как говори andriano. Это числа 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 и еще одно до 30000. Почему эти числа? Потому, что из 1 2 можно максимум составить 3; из 1 2 4 - 7; 1 2 4 8 - 15 и т.д.

я понял, что ты, говоря о переборе, имел нечто совершенно другое, чем я, хотя ты и ссылаешься на меня.
Вот я и не понял, что именно.

Я в своем сообщении имел в виду количество первых членов упорядоченной последовательности. Очевидно, они какие будут, такие и будут, и предсказать их невозможно. Под максимальным количеством же я понимал такое количество, при котором время перебора еще будет оставаться в приемлемых пределах.

Автор: S_lip 29.12.2007 17:46

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

Может, и я тебя неправильно понял.

Цитата
Задача переборная. Поэтому основная идея в решении - сократить перебираемое количество вариантов.
Для начала я бы написал функцию, которая осуществляет перебор всех возможных групп в массиве длины N, где N - входной параметр (массив может быть и глобальный).
Затем отсортировал массив чисел по возрастанию и стал последовательно вызывать функцию перебора, для возрастающих значений N, начиная с 2.
Если за некоторое количество шагов (думаю, не больше 10) искомое решение не найдено, попытался бы применить эвристику (какую - пока не знаю).

Допустим, у нас даны числа 1 3 5 7.
Ты предлагаешь сделать перебор всех возможных групп. Вот: 1 3 5 7 4 9 16 11 6 13 8 8 15 10 12.
Затем сортируем: 1 3 4 5 6 7 8 8 9 10 11 12 13 15 16.
Затем вызываем функцию перебора. Непонятно.

Может, ты имет ввиду это:
У нас есть первый элемент - 1. Начиная со второго элемента делаем полный перебор с уже имеющимися числами и сортируем их:
3) 1 3 4
5) 1 3 4 5 6 8 9
7) 1 3 4 5 6 7 8 8 9 10 11 12 13 15 16
Ответ: 8. Количество шагов: 4.

Если ты имел виду второе, от я имел ввиду тоже, что и ты.

Автор: andriano 29.12.2007 18:31

Так и не получил ответа на вопрос:

Цитата
И так же по поводу эвристик:
Какой именно из двух ваиантов тебе нужен?
1. Программа ВСЕГДА находит нужное решение. Сама программа при этом наиболее проста, но работать может до конца существования Вселенной (ну или, по крайней мере, до физического износа компа).
2. Программа, время работы которой ограничено. При этом она может выдать не то решение, которое нужно (т.е. не минимальное) или же совсем ничего не найти.
Но предполагаю, что второй вариант.
Исходя из этого я и предложил следующий алгоритм, являющийся центральной частью программы:
1. Написать процедуру, которая бы решала задачу в полном объеме, но только для части массива от 1 до K-го элемента.
2. Последовательно вызывать эту подпрограмму для упорядоченного массива, увеличивая число K (начинать с 2).

Далее я предположил, что такое решение будет укладываться в приемлемое время, вероятно, для К менее 12 (т.е. 10 шагов от 2 до 11).

По поводу самого перебора примерно так:
M - максимальная сумма, присваиваем 100000
- перебор по К от 2 до N
-- перебор по всем возможным группам (1-я группа) с количеством элементов от 1 до К-1 (в пределах первых К элементов)
--- в случае, если сумма чисел в группе не больше М, то
---- перебор по всем возможным группам (2-я группа), которые можно сформировать из оставшихся элементов (в пределах первых К)
----- сравнение сумм чисел в группах, если равны, то запоминаем и переопределяем М новой суммой-1

PS. Алгоритма, который предлагаешь ты, я так и не понял.

Автор: S_lip 30.12.2007 19:32

andriano, мне не нужен ни один из предложенных вариантов. Мне нужно, что программа всегда давала правильный ответ за ограниченное время работы (не дольше 1 секунды). Именно такой программой и является мой последний выложенный код.

Ко всем: если кто может, помогите найти такие входные файлы, чтобы эта программа давала неправильный ответ, т.к. все тесты, которые я пробовал, она проходила на "ура".

Вот небольшое разъяснение работы моего кода, которое поможет вам в ней разобраться и, возможно, найти такую цепь, при которой прога давала бы неправильный ответ.
1) Массивы "u" и "d" содержат все возможные минимальные наборы чисел от 1 до i элемента в цепи. Причем для удобства u[num]<=d[num].
2) Под минимальными имеется ввиду следующее: например сдери массивов уже имеются такие пары: u[num1]=1 d[num1]=8 и u[num2]=0 d[num2]=7. Первая пара нам не нужна, т.к. если следующая i будет 7, то в качестве ответа подойдет и 7 (0+7=7) и 8 (1+7=8). Поэтому после всех добавления в массивы u и d всех новых пар с участием i, идет отсеивание ненужных пар.
3) Чтобы каждый раз не сортировать массивы u и d, используется массив b, каждый элемент которого указывает на пару в массива u и d с соответствующей разностью. Например, в случае с u[num1]=1 d[num1]=8 и u[num2]=0 d[num2]=7, b[8-1]=num1, а b[7-0]=num2. Понятно, что b[7] может хранить только одно значение. В нашем случае - b[7]=num2, т.к. u[num2]=0 d[num2]=7 - минимальны.

Разберем пример цепи из 4-ех чисел: 1 3 5 7.
1) сначало копируем первый элемент(1):
u d
0 1
b= ( 0,1,0,0,0,0,0,0...). Именно так потому, что d[1]-u[1]=1, а массив b начинается с 0-ого элемента.
2) второй элемент(3):
u d
0 1 - этот был.
0 3 - этот добавляем с учетом, что ответ будет включать в себя 2-ой эл-т, но не будет то, что было.
0 4 - один набор включает то, что было в d + 3, а второй - то, что было в u.
1 3 - наобарот. один набор включает то, что было в u + 3, а второй - то, что было в d. Переверачиваем,т.к. u[4]>d[4].
b= ( 0,1,4,2,3,0,0,0...).
3) третий элемен(5):
u d
0 1 - был.
0 3 - был.
0 4 - был.
1 3 - был.
0 5 - этот добавляем с учетом, что ответ будет включать в себя 3-ий эл-т, но не будет то, что было.
0 6 - один набор включает то, что было в d[1] + 5, а второй - то, что было в u[1].
1 5 - наобарот. один набор включает то, что было в u[1] + 5, а второй - то, что было в d[1]. Переверачиваем,т.к. u[8]>d[8].
0 8 - u[2]/d[2]+5.
3 5 - u[2]+5/d[2]. Переворачиваем.
0 9 - u[3]/d[3]+5.
4 5 - u[3]+5/d[3]. Переворачиваем.
1 8 - u[4]/d[4]+5.
3 6 - u[4]+5/d[4]. Переворачиваем.
Теперь отсеиваем ненужные: 1/5 (т.к. есть 0/4), 3/5 (есть 1/3), 4/5 (0/1), 3/6 (0/3).
Получаем:
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
b= (0,1,4,2,3,5,6,7,8,9)
4) четвертый элемен(7):
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
0 7
0 8
1 7
0 10
3 7
0 11
4 7
1 10
3 8
0 12
5 7
0 13
6 7
0 15
7 8
0 16
7 9
1 15
8 8
Отсеиваем ненужные. Получаем:
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
0 7
0 10
0 11
0 12
0 13
0 15
0 16
1 15
8 8
b= (18,1,4,2,3,5,6,9,7...)
Ура! b[0]>0. ответ: u[b[0]]. т.е. - 8

Автор: Michael_Rybak 30.12.2007 21:00

Во-первых, посыпая голову пеплом, вынужден признать, что задача ни разу не NP-полная.

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

Проблема в массиве b. Дело в том, что он хранит "указатели" на первый попавшийся результат для данной разницы. А тебе нужен не любой, а наименьший (т.е. с наименьшей суммой).

Вот тебе тест:

Код
6
11
70
80
90
100
111


Сумма 170 = 70 + 100 = 80 + 90 будет найдена первой, тогда как есть еще сумма 111 = 100 + 11.

Удачи smile.gif Скажешь, когда зааксептишь.

Автор: andriano 30.12.2007 21:13

Цитата
andriano, мне не нужен ни один из предложенных вариантов. Мне нужно, что программа всегда давала правильный ответ за ограниченное время работы (не дольше 1 секунды). Именно такой программой и является мой последний выложенный код.
Похоже, что так.
Сейчас прикинул, - действительно, при ограничениях на величину числа последовательность, заведомо содержащая хотя бы одну пару требуемых наборов не превосходит 16 штук. Т.е. 200 - явно избыточное значение. Действительно, достаточно рассматривать 16 первых членов упорядоченной последовательности.
Решения, честно говоря, не понял. Сам бы делал по-другому и совершенно неочевидно, что это было бы оптимальнее.

PS. На всякий случай позволю себе процитировать себя же (пост #7):
Цитата
Да, и еще:
Перебор рано заканчивать, если найдено решение, при котором в обеих группах более одного элемента, - необходимо продолжить его до тех пор, пока в рассмотрении не будет участвовать максимальное число, не превосходящее эту сумму.


Автор: Michael_Rybak 30.12.2007 22:16

Его решение оптимально, поэтому твое в лучшем случае имело бы лучшую константу, и такую же асимптотику.

Цитата
Сам бы делал по-другому и совершенно неочевидно, что это было бы оптимальнее.

Очевидно, потому что твое - экспоненциальное, его - полиномиальное.

Цитата
Решения, честно говоря, не понял.

Смотри. Как бы мы не выбирали числа для первой и второй суммы, мы никогда не вылезем за 100000 ни в одной из сумм (если вылазим, можно игнорировать такую выборку).

Пусть мы кладем гири на весы, а не даем деньги детям (мне так удобнее).

Заведем массив can_achieve_difference[-100000 .. 100000] of boolean, заполним его false'ами.

Теперь по очереди решим следующие подзадачи:

Какие разницы между левой и правой чашей можно получить, если у нас есть только первая гирька? Только первые две? Только первых три? И т.д.

Чтобы узнать, какие разницы можно получить, используя только первые k+1 гирек (но не обязательно все k+1, конечно), нужно (k+1)-ю гирьку Х добавить ко всем найденым на данный момент разницам, и отнять от всех найденых разниц, а также учесть разницы Х и -Х.

// схематически

fillchar(can_achieve_difference_next_step, false);

can_achieve_difference_next_step[X] := true; // только эта гирька на правой чаше
can_achieve_difference_next_step[-X] := true; // только эта гирька на левой
for i := -100000 to 100000 do
can_achieve_difference_next_step :=
can_achieve_difference[i-x] // на левую чашу?
or can_achieve_difference[i + x] // на правую?
or can_achieve_difference[x]; // не используем вообще?

move(can_achieve_difference, can_achieve_difference_next_step);
// на самом деле, второй массив не нужен, так как старые значения true остаются на месте. но так - понятнее

Как только can_achieve_difference[0] станет равен true, это будет означать, что решение существует.

Такой подход не учитывает, что нас интересует минимальная сумма весов гирек, и не дает возможности восстановить найденое решение. Чтобы это учесть, нужно хранить не только true/false, а еще и минимальный вес и последнюю использованную гирьку.

Автор: andriano 30.12.2007 23:13

Спасибо, идею алгоритма понял.

Цитата(Michael_Rybak @ 30.12.2007 18:16) *

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

Смотри. Как бы мы не выбирали числа для первой и второй суммы, мы никогда не вылезем за 100000 ни в одной из сумм (если вылазим, можно игнорировать такую выборку).

Пусть мы кладем гири на весы, а не даем деньги детям (мне так удобнее).
И это правильно - свои деньги никому не отдам! ;)
Цитата

Заведем массив can_achieve_difference[-100000 .. 100000] of boolean, заполним его false'ами.
А почему бы не ограничиться от 0 до 100000? Из соображений симметрии?
Цитата

Теперь по очереди решим следующие подзадачи:

Какие разницы между левой и правой чашей можно получить, если у нас есть только первая гирька? Только первые две? Только первых три? И т.д.
Дачинать меньше чем с 2 не имеет смысла. Впрочем, об этом я уже писал.
Цитата

Чтобы узнать, какие разницы можно получить, используя только первые k+1 гирек (но не обязательно все k+1, конечно), нужно (k+1)-ю гирьку Х добавить ко всем найденым на данный момент разницам, и отнять от всех найденых разниц, а также учесть разницы Х и -Х.
Согласен.
Собственно, предлагаемый мною раньше перебор с двумя циклами можно упростить: каждую из гирек умножать на одну из рех констант: -1, 0 или +1. Перебор сложноси 3^N. Для 16 это примерно 43 млн, что на поряыдок меньше оценки в 3 млн для описанного тобой варианта, но:
1. Не требует дополнительных массивов.
2. Сразу обнаруживаем все элементы, входящие в суммы.
3. Весьма вероятно, что перебор закончится задолго до достижения 3^N. Тем более, что существует очевидное условие, ограничивающее глубину перебора.

Еще раз спасибо.

Автор: Michael_Rybak 31.12.2007 0:07

Цитата
А почему бы не ограничиться от 0 до 100000? Из соображений симметрии?

Дачинать меньше чем с 2 не имеет смысла. Впрочем, об этом я уже писал.

1. Не требует дополнительных массивов.
2. Сразу обнаруживаем все элементы, входящие в суммы.

В приведенном мной объяснении многое описано не совсем так, как я бы делал на практике, да.

Цитата
Перебор сложноси 3^N. Для 16 это примерно 43 млн

А как быть с тестом, в ответе которого участвует большее количество элементов? Почти уверен, что можно составить тест, для которого понадобится и около 40.

Цитата
Еще раз спасибо.

Всегда рад smile.gif

Автор: andriano 31.12.2007 0:21

Цитата(Michael_Rybak @ 30.12.2007 20:07) *

В приведенном мной объяснении многое описано не совсем так, как я бы делал на практике, да.
Логично.
Цитата

А как быть с тестом, в ответе которого участвует большее количество элементов? Почти уверен, что можно составить тест, для которого понадобится и около 40.
Всегда рад smile.gif
А я думаю, что невозможно больше 16. Об этом, кстати, S_lip писал.
Т.е. при заданных ограничениях первые 16 упорядоченного массива ВСЕГДА будут содержать минимум одну искомую группу.
Впрочем, возможно, я и ошибаюся. Просто я не могу придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.

Автор: Michael_Rybak 31.12.2007 0:25

Цитата
придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.


сейчас попробуем.

Автор: Michael_Rybak 31.12.2007 0:49

выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум. мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.

Автор: andriano 31.12.2007 2:50

Цитата(Michael_Rybak @ 30.12.2007 20:49) *

выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.
Жду с интересом.
PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штук
Цитата

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум.
Не нужно. Сортируем по возрастанию и перебираем не более 16 первых.
Цитата
мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.
Ну, можно начать с нескольких эвристик. Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.

Автор: Michael_Rybak 31.12.2007 3:22

Цитата
PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штук


Ну 15. Какая разница.

Цитата
Не нужно. Сортируем по возрастанию и перебираем не более 16 первых.


Это не обязательно правильно.

Цитата
Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.


Можешь написать и попросить ОП проверить на сайте.

Автор: S_lip 31.12.2007 21:03

Michael_Rybak, спасибо за пример.
Вот исправленный код:

const
MaxCount=200;
MaxSum=100000;
type
posanddif=record
c,d:longint;
end;
var
a:array [1..MaxCount] of integer;
n:byte;
u,d:array [1..(MaxSum div 2)] of longint;
udn:longint;
b:array [0..(MaxSum div 2)] of longint;
pad:array [1..(MaxSum div 2)] of posanddif;
pn:longint;
f:text;
i,j:longint;

procedure ProcessUD(uu,dd:longint);
var
ii:longint;
begin
if dd<=(MaxSum div 2) then begin
if b[dd-uu]>0 then begin
if u[b[dd-uu]]>uu then begin
ii:=1;
while (ii<=pn) and (pad[ii].c<>b[dd-uu]) do inc(ii);
if ii>pn then begin
inc(pn);
pad[pn].c:=b[dd-uu];
pad[pn].d:=u[b[dd-uu]]-uu;
end else if pad[ii].d>u[b[dd-uu]]-uu then
pad[ii].d:=u[b[dd-uu]]-uu;
end;
end else begin
inc(udn);
u[udn]:=uu;
d[udn]:=dd;
b[dd-uu]:=udn;
end;
end;
end;

begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do
readln(f,a[i]);
close(f);

for i:= 0 to (MaxSum div 2) do b[i]:=0;
udn:=1;
i:=1;
u[1]:=0;
d[1]:=a[1];
b[a[1]]:=a[1];

for i:= 2 to n do begin

pn:=0;
j:=udn;

ProcessUD(0,a[i]);

for j:= 1 to j do begin
ProcessUD(u[j],d[j]+a[i]);
if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
else ProcessUD(d[j],u[j]+a[i]);
end;

for j:= 1 to pn do begin
dec(u[pad[j].c],pad[j].d);
dec(d[pad[j].c],pad[j].d);
end;

end;
writeln(u[b[0]]); //ответ
end.


Главное отличие - обходим все элементы, а также убрана медленная проверка в конце главного цикла и добавлен массив pad, который содержит позицию "с" и разницу "d" тех элементов, для которых мы нашли замену.
Этот пример также навел на мысль, что максимальное количество перебираемых чисел будет не 15 и не 16, а... 7502 (1 15000 15002 15004 ... 29998 29999). Поэтому нужно перебирать все n. Однако прога не справилась с примером из 200 чисел (1 200 202 204 ... 594 595). udn выходит за пределы 50000. Ошибка 201. Я потратил достаточно много времени, чтобы найти, где промах, но безуспешно.
Этот пример в 200 чисел прикреплен.


Прикрепленные файлы
Прикрепленный файл  file.in.txt ( 1003 байт ) Кол-во скачиваний: 246

Автор: Michael_Rybak 31.12.2007 21:27

на самом деле 15.

1 15000 15002 15004 ... 29998 29999- если ты имел ввиду все четные, начиная с 15000, то сразу же получится 15000+15006 = 15002+15004.

ночью посмотрю, где ошибка.

Автор: S_lip 31.12.2007 22:49

15000+15006 = 15002+15004 = 30006
1+29998 = 29999

Автор: Michael_Rybak 1.01.2008 2:35

А, теперь я понял, к чему этот пример был.

Отличная мысль.

andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.

Автор: S_lip 1.01.2008 22:31

Спасибо большое всем, кто потратил свое время читая это все и пытался помочь...
Я нашел решение:

const
MaxCount=200;
MaxSum=100000;
type
posanddif=record
c,u:longint;
end;
var
a:array [1..MaxCount] of integer;
n:byte;
u,d,b:array [0..(MaxSum div 2)] of longint;
udn:longint;
pad:array [1..(MaxSum div 2)] of posanddif;
pn:longint;
f:text;
i,j:longint;

procedure ProcessUD(uu,dd:longint);
begin
if dd<=(MaxSum div 2) then begin
if b[dd-uu]>0 then begin
if u[b[dd-uu]]>uu then begin
inc(pn);
pad[pn].c:=b[dd-uu];
pad[pn].u:=uu;
end;
end else begin
inc(udn);
u[udn]:=uu;
d[udn]:=dd;
b[dd-uu]:=udn;
end;
end;
end;

begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do
readln(f,a[i]);
close(f);

for i:= 0 to (MaxSum div 2) do b[i]:=0;
udn:=0;
i:=1;
u[0]:=0;
d[0]:=a[1];
b[a[1]]:=a[1];

for i:= 2 to n do begin

pn:=0;
j:=udn;

ProcessUD(0,a[i]);

for j:= 0 to j do begin
ProcessUD(u[j],d[j]+a[i]);
if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
else ProcessUD(d[j],u[j]+a[i]);
end;

for j:= 1 to pn do begin
if pad[j].u<u[pad[j].c] then begin
dec(d[pad[j].c],u[pad[j].c]-pad[j].u);
u[pad[j].c]:=pad[j].u;
end;
end;

end;

writeln(u[b[0]]);
end.

Ошибка 201 была из-за того, что элементы массивов u и d могу принимать значения от 0 до 50000. Т.е. всего 50001 значение. Изменение начала массивов на 0-ой элемент решило проблему. Также убрана ошибка в ProcessUD, долгий цикл "for ii:= 1 to pn" перенесен в конец главного цикла в виде проверки "if pad[j].u<u[pad[j].c]".
В тестере все примеры решены.

P.S.: С новым годом =)

Автор: Michael_Rybak 2.01.2008 8:29

Отлично, поздравляю.

Приходи еще smile.gif

Автор: andriano 2.01.2008 16:46

Цитата(Michael_Rybak @ 31.12.2007 22:35) *
andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.
Спасибо, я заметил. smile.gif
Кстати, к вопросу об эвристиках:
Решения вида a[n]=a[m] находятся (после сортировки) за O(N), вида a[n]=a[m]+a[k] за O(N*log(N)), a[n]+a[m]=a[k]+a[l] и a[n]=a[m]+a[k]+a[l] - за O(N^2*log(N)).
Правда:
1, 2, 4, 8, 16, 32, 64, 15000, 15128, 15256, ... 29848, 29975 содержит 125 чисел и находится только степенной эвристикой аналогичной тем, что приведены выше, O(N^7*log(N)).

В этой связи возникает еще одна интересная задача: подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения. Заодно интересно было бы оценить минимально необходимое количество тестов в этом наборе.

Автор: Michael_Rybak 2.01.2008 19:50

Цитата
подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения

Такая задача возникает всегда. Именно поэтому уровень тех, кто предлагает задачи на олимпиаду, должен как минимум не уступать уровню участников, а в идеале - быть на порядок выше. Как, кстати, и бывает на всероссийской олимпиаде школьников, где каждая задача проходит через семь кругов ада, прежде чем попасть на тур.