ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска суммы
25 сообщений из 117, страница 2 из 5
  2  все
Алгоритм поиска суммы
    #36679164
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
Альмалексия,

пока минимум не найдем :).
...
Рейтинг: 0 / 0
09.06.2010, 19:54:01
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36679437
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
рстудио,

а вы сами то свой код тестировали? Если да, то что у вас вышло? У меня с вашим кодом получается 26 шагов по 2.6 и 4 шага по 0.7, что есть 70.4. ???
...
Рейтинг: 0 / 0
09.06.2010, 22:40:30
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36679631
teras
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
teras
Гость
Прошу прощения за безыскусное решение конкретно этой задачи - как-то не хотелось применять общие методы без особой нужды. Но зато у него есть большой плюс - оно быстро работает (максимум - один рекурсивный вызов), памяти, соответственно, не жрет и для указанных коэффициентов всегда находит оптимальное решение по кол-ву шагов. Возможно не оптимальное, но близкое - доказывать лениво как-то.

Идея заключается в том, что для четных значений легко вычисляется оптимум используя коэффициенты 2.6; 2 * 0.7 = 14; 0.2. 1.3 не нужен - потому что 2*1.3 = 2.6. А для нечетных чисел производится попытка выбрать оптимальный коэффициент приведения к четному - то есть - оценить, что лучше вычесть 1.3, 0.7 или 1. Последний применяется только для чисел меньших 0,7 (что приведет к потере точности). Для всех остальных чисел (больше или равным 0,7) алгоритм позволяет всегда получить точное значение.

Значения задаются в целых числах, умноженные на 10. то есть 86,5 задается как 865.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
#define odd(x)	(((x) %  2 ) ==  1 )

typedef struct
{
    int s02;
    int s07;
    int s13;
    int s26;
} Steps;

int
step_count(const Steps * steps)
{
    return steps->s02 + steps->s07 + steps->s13 + steps->s26;
}

void
gen( int num, Steps * steps )
{
    if (odd(num)) {
        if (num >=  13 ) {
            /* two ways are possible, check both*/
            Steps s2 = { 0 };
            
            steps->s13 ++;
            s2.s07 ++;
            
            gen(num -  13 , steps);
            gen(num -  7 ,  &s2);
            
            if (step_count(steps) > step_count(&s2))
                *steps = s2;
            return;
        } else {
            if (num >=  7 ) {
                steps->s07++;
                num -=  7 ;
            } else
                num--;
        }
    }
    
    /* num is even */
    if (num >=  26 ) { steps->s26 += num /  26 ; num -=  26  * (num /  26 ); }
    if (num >=  14 ) { steps->s07 +=  2  * (num /  14 ); num -=  7  *  2  * (num /  14 ); }
    steps->s02 += num /  2 ;
}
...
Рейтинг: 0 / 0
10.06.2010, 02:24:31
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680141
Alexey Koptenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexey Koptenkov
Гость
Задача о рюкзаке..
...
Рейтинг: 0 / 0
10.06.2010, 11:49:51
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680306
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
mikhail_nрстудио,

а вы сами то свой код тестировали? Если да, то что у вас вышло? У меня с вашим кодом получается 26 шагов по 2.6 и 4 шага по 0.7, что есть 70.4. ???

Лень было посчитать :)

теперь все чики-поки :)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
 Private Function Find(ByRef valueList As List(Of Decimal), _
                          ByRef wayList As List(Of Decimal), _
                          ByVal currValue As Decimal, _
                          ByVal targetValue As Decimal) As Boolean

        For Each value As Decimal In valueList
            currValue += value

            'save way list
            wayList.Add(value)

            Dim ret As Boolean
            If (currValue = targetValue) Then
                ret = True
            ElseIf currValue > targetValue Then
                ret = False
            Else
                ret = Me.Find(valueList, wayList, currValue, targetValue)
            End If

            If ret Then
                Return True
            Else
                wayList.RemoveAt(wayList.Count -  1 )
            End If

            currValue -= value
        Next

        Return False
    End Function
...
Рейтинг: 0 / 0
10.06.2010, 12:29:26
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680329
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Mozokrstudio,

загони код в Ворд и посчитай символы.

Вы действительно решили мерятся кодом ?
Я давно хотел померять код в процедурном языке с чемто функциональным. Во мне давно теплится мысль что в функциональном программировании программы частенько выходят банально длинее. Я уже не говорю о том что сложнее :)
...
Рейтинг: 0 / 0
10.06.2010, 12:35:48
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680378
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
rstudio,

"внатуре" решил померяться :).
Прошу ваш пример на шарпе, ибо примеры на бейсике больше в 2 раза.
...
Рейтинг: 0 / 0
10.06.2010, 12:50:57
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680460
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Код: plaintext
1.
int F(L vl,L wl,L cv,L tv){int r;foreach(decimal v in vl){wl.Add(v);if(cv+v==tv) r = 1;else if(cv+v<tv)r = F(vl, wl, cv+v , tv);if (r) break;else wl.RemoveAt(wl.Count - 1);}return r;}
чтож, поехали версия компакт эдишн намбер ван бай сишарп, 186 byte VS 336 byte в нашу пользу
...
Рейтинг: 0 / 0
10.06.2010, 13:12:20
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680492
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
rstudio,

а этот код хоть работает :)? Вот, навскидку, уже в объявлении йункции тип переменных L - это что такое?
Да и переменная r ничем не инициализируется. Вы ошибочки поправьте-то.
...
Рейтинг: 0 / 0
10.06.2010, 13:23:15
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680562
Тыжных Иван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тыжных Иван
Участник
admiral.diver,


Ограничения
0.2a + 0.7b + 1.3c + 2.6d=86
a>=0
b>=0
c>=0
d>=0
a,b,c,d - целые

Целевая функция a+b+c+d >= min

Ну а дальше симплекс-метод и его частный случай с условием на целостность переменных.

Так, не?
...
Рейтинг: 0 / 0
10.06.2010, 13:47:10
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680699
Тыжных Иван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тыжных Иван
Участник
Тыжных Иванadmiral.diver,


Целевая функция a+b+c+d -> min
...
Рейтинг: 0 / 0
10.06.2010, 14:32:19
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680711
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Mozokrstudio,

а этот код хоть работает :)? Вот, навскидку, уже в объявлении йункции тип переменных L - это что такое?
Да и переменная r ничем не инициализируется. Вы ошибочки поправьте-то.

работает работает :)

Код: plaintext
1.
class L:List<decimal>{}; int F(L a, L b, L c, L d){int r= 0 ;foreach(decimal v in a){b.Add(v);if(c+v==d)r= 1 ;else if(c+v<d)r=F(a,wl,c+v,d);if(r)break;else wl.RemoveAt(b.Count- 1 );}return r;}

186 байт как и было :)
...
Рейтинг: 0 / 0
10.06.2010, 14:36:06
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680733
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
rstudio
Код: plaintext
1.
class L:List<decimal>{}; int F(L a, L b, L c, L d){...foreach(decimal v in a){...if(c+v==d)...

Это нормально - суммировать число и список ?
...
Рейтинг: 0 / 0
10.06.2010, 14:41:41
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680798
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Mozokrstudio,

а этот код хоть работает :)? Вот, навскидку, уже в объявлении йункции тип переменных L - это что такое?
Да и переменная r ничем не инициализируется. Вы ошибочки поправьте-то.

работает работает :)

Код: plaintext
1.
class L:List<decimal>{}; int F(L a, L b, L c, L d){int r= 0 ;foreach(decimal v in a){b.Add(v);if(c+v==d)r= 1 ;else if(c+v<d)r=F(a,wl,c+v,d);if(r)break;else wl.RemoveAt(b.Count- 1 );}return r;}

186 байт как и было :)
...
Рейтинг: 0 / 0
10.06.2010, 14:55:17
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680843
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Mozokrstudio,

а этот код хоть работает :)? Вот, навскидку, уже в объявлении йункции тип переменных L - это что такое?
Да и переменная r ничем не инициализируется. Вы ошибочки поправьте-то.

работает работает :)

Код: plaintext
1.
class L:List<decimal>{}; int F(L a, L b, L c, L d){int r= 0 ;foreach(decimal v in a){b.Add(v);if(c+v==d)r= 1 ;else if(c+v<d)r=F(a,wl,c+v,d);if(r)break;else wl.RemoveAt(b.Count- 1 );}return r;}

186 байт как и было :)
...
Рейтинг: 0 / 0
10.06.2010, 15:08:44
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680847
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
пардон, интернет заглючил :)
...
Рейтинг: 0 / 0
10.06.2010, 15:09:17
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680849
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Mozokrstudio
Код: plaintext
1.
class L:List<decimal>{}; int F(L a, L b, L c, L d){...foreach(decimal v in a){...if(c+v==d)...

Это нормально - суммировать число и список ?

так ну ты уже не придирайся, давай свою версию. Мне после каждого чиха оптимизаций по коду лениво перепроверять, но не волнуйся, опечатки механические, алгоритм эквивалентен с васиковским Если нужно будет, отладим :)
...
Рейтинг: 0 / 0
10.06.2010, 15:11:18
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36680875
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
rstudio,

дык, я и не придираюсь. Просто хочу увидеть рабочую версию.
Мой код вот работает без всякой отладки.
...
Рейтинг: 0 / 0
10.06.2010, 15:18:36
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681541
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Есть такая рабочая версия и все теже <190 байт.
ЗЫ:
Вообщем я бы не тратил время на отладку, отладку можно провести в конце, просто для контроля
что оптимизация не была достигнута в счет утраты работоспособности.

итак счет 190/365 пользу шарпа. Ваш ход

 
190_байт
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace WindowsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            List<decimal> l = new List<decimal>();
            l.Add( 2 .6m);
            l.Add( 1 .3m);
            l.Add( 0 .7m);
            l.Add( 0 .2m);

            List<decimal> w = new List<decimal>();
            F(l, w,  0 ,  86 );

            //w - тут будет результат
        }



        int F(List<decimal> a, List<decimal> b, decimal c, decimal d) { int r =  0 ; foreach (decimal v in a) { b.Add(v); if (c + v == d)r =  1 ; else if (c + v < d)r = F(a, b, c + v, d); if (r== 1 )break; else b.RemoveAt(b.Count -  1 ); } return r; }
    }
}
...
Рейтинг: 0 / 0
10.06.2010, 20:08:49
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681594
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
тут еще глянул, два else там не нужны. 185 байт.
...
Рейтинг: 0 / 0
10.06.2010, 20:44:50
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681609
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
rstudio,

изменил в вашей программе 86 на 85,05. Получил зависание.
Уверяю, что у меня такого не произойдет :).
...
Рейтинг: 0 / 0
10.06.2010, 21:00:49
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681625
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
Mozokrstudio,

изменил в вашей программе 86 на 85,05. Получил зависание.
Уверяю, что у меня такого не произойдет :).

Это шутка наверное такая. Счастливые обладатели компилятора Лиспа или чего то там думают что их корч работает наверное на квантовых процессорах

ЗЫ: Для задачи не имеющей решение программа не зависает, а оставив эвристику уходит в полный перебор комбинаций. Решения для чисел с нормальным десятичным знаком ( как по условию задачи ) решения находятся в доли секунды.

ЗЫЗЫ: Все еще с надеждой увидеть версию в в 185-1 байт :)
...
Рейтинг: 0 / 0
10.06.2010, 21:14:10
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681653
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
кстате, проревьювил тут ваш код. Что это за рассово неправильные обьявления за пределами функции. Повод для оптимизации моего кода, 153 байта уже :)
...
Рейтинг: 0 / 0
10.06.2010, 21:42:07
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681772
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
rstudio153 байта уже :)размер файла проекта и то что студия нагенерила не учитываем, да? ;-))
...
Рейтинг: 0 / 0
11.06.2010, 00:27:29
| Ответить | Цитировать | Написать  
Алгоритм поиска суммы
    #36681783
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
egorychrstudio153 байта уже :)размер файла проекта и то что студия нагенерила не учитываем, да? ;-))

а зачем его учитывать ?
...
Рейтинг: 0 / 0
11.06.2010, 00:46:51
| Ответить | Цитировать | Написать  
25 сообщений из 117, страница 2 из 5
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска суммы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36680849&tid=1343597]:
 0ms
get settings:
 9ms
get forum list:
 19ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 394ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 71ms
get tp. blocked users:
 1ms
others: 235ms
total:  747ms
созд. / загр.: 747ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]