IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Нахождение двух минимальных сумм чисел
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


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

Дана упорядоченная последовательность 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 вылетает. Возможно, есть более элегантное и правильное решение? =)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Любые решения этой задачи будут эвристическими, поскольку она NP-полная.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Непонятно условие:
- что такое набор чисел?
- почему сначала о величинах говорится во множественном числе, а потом фигурирует "эта величина", которая, кстати, может достигать 100000, тогда как числа ограничены 30000?
- чем группа числе отличается он "не группы"? Как определить границы группы?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


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).

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

Сообщение отредактировано: S_lip -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

Честно говоря не имею опыта в подобных оценках, но у меня складывается впечатление, что эта задача скорее олимпиадная, чем учебная. Поэтому, извини, вопрос: откуда она появилась?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


andriano, нет это ты меня извини, что задачу описал не информативно.
Задача взята с латвийского портала по олимпиадным задачам.
Если она очень мешает в ветке задач, то я могу поместить в тему "олимпиадные задачи".

Сорри, если что не так.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

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


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

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

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

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

Сообщение отредактировано: andriano -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


в общем вот грубый перебор 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.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


Спасибо всем большое за ответы!
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 и т.д.

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

Сообщение отредактировано: S_lip -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Не мог бы ты объяснить, почему надо перебирать именно эти числа? Во входном файле может не оказаться ни одного из них.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


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

Сообщение отредактировано: S_lip -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Не понял.
Прочитав эту фразу:
Цитата
По моим подсчетам, максимальное количество чисел, которые нужно будет перебирать, будет 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 и т.д.

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

Я в своем сообщении имел в виду количество первых членов упорядоченной последовательности. Очевидно, они какие будут, такие и будут, и предсказать их невозможно. Под максимальным количеством же я понимал такое количество, при котором время перебора еще будет оставаться в приемлемых пределах.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


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

Может, и я тебя неправильно понял.
Цитата
Задача переборная. Поэтому основная идея в решении - сократить перебираемое количество вариантов.
Для начала я бы написал функцию, которая осуществляет перебор всех возможных групп в массиве длины 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.

Если ты имел виду второе, от я имел ввиду тоже, что и ты.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

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

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

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

Сообщение отредактировано: andriano -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

Код
6
11
70
80
90
100
111


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

Удачи smile.gif Скажешь, когда зааксептишь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

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



Сообщение отредактировано: andriano -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

Смотри. Как бы мы не выбирали числа для первой и второй суммы, мы никогда не вылезем за 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, а еще и минимальный вес и последнюю использованную гирьку.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Спасибо, идею алгоритма понял.
Цитата(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. Тем более, что существует очевидное условие, ограничивающее глубину перебора.

Еще раз спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

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

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

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

Всегда рад smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 16:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name