Форум программистов, компьютерный форум CyberForum.ru

Программа по резке труб - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 18:44     Программа по резке труб #1
Всем доброе время суток, помогите, пожалуйста, решить задачу (друг попросил написать программу,а сам осилить не могу). Парень работает в фирме, которая изготавливает двери для лифтов.
Задача: Есть трубы(заготовки)длину которых мы знаем(обычно 288 дюймов), есть ширина реза пилы, которую мы тоже знаем (обычно 0,18 дюйма).Ему порезать несколько таких заготовок,чтобы сделать тележку(количество и длины получаемых труб мы можем вводить каждый раз разные). Он вводит:
1. длину заготовки
2. ширину реза пилы
3. сколько труб и какой длины ему нужно получить
Конкретный пример:
1.Длина заготовки 288 дюймов
2. Ширина реза пилы 0,18 дюйма
3.Длина труб и их количество :
40 дюймов -3 шт
45 дюймов - 5 шт
42 дюйма - 6 шт
70 дюймов - 3 шт
52,5 дюйма - 2 шт
14,5 дюйма - 3 шт
Нужно,чтобы программа просчитала сколько нужно будет таких заготовок и оптимальную последовательность (в каком порядке нужно резать трубы,чтобы получить минимальный отход с каждой заготовки).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.07.2016, 18:44     Программа по резке труб
Посмотрите здесь:

C++ Выяснить, имеет ли место пересечение кусков труб

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,120
Записей в блоге: 2
24.07.2016, 19:18     Программа по резке труб #2
Цитата Сообщение от Hevzy86 Посмотреть сообщение
минимальный отход с каждой заготовки
критерий неформализованный. Ежу понятно, что если надо нарезать в общей длине 80 метров труб от двух заготовок по 50 метров (пренебрегая шириной реза для простоты), то отходов получим 20 метров. А как оптимальнее их распределить на 2 трубы - по 10 метров с каждой или 18 с одной и 2 с другой - это критерием не оговаривается.
Peoples
715 / 375 / 339
Регистрация: 06.02.2016
Сообщений: 989
Записей в блоге: 10
Завершенные тесты: 3
24.07.2016, 19:22     Программа по резке труб #3
Hevzy86, Допустим для этого примера материала надо: 40*3+45*5+42*6+70*3+52,2*2+14,5*3=954,9 дюймов надо. Заготовка 288 дюймов, значит 954,9/288=3,315, получается, если округлить 4 заготовки, отходов 197,1 дюйм. Разъясните момент с шириной реза, что это и как влияет на отход, или на что-нибудь и про то, что подразумевается под оптимальностью?
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 19:31  [ТС]     Программа по резке труб #4
Peoples, Как мне объяснил "заказчик", распределение резки труб и является важным(чтоб получить наименьший остаток), извиняюсь, может я не совсем точно описал задачу

Добавлено через 2 минуты
_Ivana, ширину реза надо добавлять к каждой отрезанной трубе, т.к. это ширина самой пилы и, соответственно, эта ширина реза каждый раз когда пила режет металл, просто отнимается от исходной заготовки. Оптимальностью является то,чтобы с каждой заготовки было как можно меньше отходов(т.е. как можно меньше металла выбрасывалось)
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6160 / 2889 / 282
Регистрация: 04.12.2011
Сообщений: 7,689
Записей в блоге: 3
24.07.2016, 19:44     Программа по резке труб #5
Цитата Сообщение от Hevzy86 Посмотреть сообщение
(в каком порядке нужно резать трубы,чтобы получить минимальный отход с каждой заготовки
Это неправильное условие (имхо). Наиболее рационально получить:
Цитата Сообщение от Hevzy86 Посмотреть сообщение
минимальный отход с каждой заготовки
кроме последней. То есть, вариант когда на 10 заготовок пришлось в среднем по 20'' отхода, хуже чем если весь отход пришёлся на последнюю заготовку и составил 200''. Так конечно не бывает и по заготовкам будет по мелочи какой-то отход тоже, но нужно стремиться к тому, чтобы отход последней заготовки (последней - для определённости, главное что одной) был максимален.
При такой постановке это вполне рутинная задача.
Цитата Сообщение от Hevzy86 Посмотреть сообщение
ширину реза надо добавлять к каждой отрезанной трубе
Если нужно n кусков, то будет n-1 резов. То есть, не на каждую. Но это не страшно.
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 19:57  [ТС]     Программа по резке труб #6
IGPIGP,можно и так попробовать,как вы говорите, думаю,неплохо будет. Но у меня знаний и практики не хватает,как это реализовать(если поможете,буду рад), а насчет n-1 резов, согласен
Peoples
715 / 375 / 339
Регистрация: 06.02.2016
Сообщений: 989
Записей в блоге: 10
Завершенные тесты: 3
24.07.2016, 22:31     Программа по резке труб #7
Не уверен в правильности, надо тестировать
C++
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<vector>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
    setlocale(LC_ALL,"RUS");
    vector<double>val; // вектор дюймов
    vector<int>v; // вектор штук
    vector<double>sum; // сумма дюймов, то есть дюймы* количество 
    // начало
    double zagotovka; // длина заготовки
    double raz;   // длина реза 
    cout<<"Введите длину заготовки: "<<endl;
    cin>>zagotovka;
    cout<<"Введите ширину реза: "<<endl;
    cin>>raz;
    cout<<"Введите сколько категорий труб будет: "<<endl;  // сколько вариант труб разных дюймов 
    int t;
    cin>>t;
    for(int i=0; i<t; i++) {       // вводим данные 
        double dl; 
        double st;
        cout<<"Введите длину трубы: "<<endl;
        cin>>dl;
        val.push_back(dl);
        cout<<"Введите сколько таких труб надо : "<<endl;
        cin>>st;
        v.push_back(st);
        cout<<endl;
    }
 
    for(int i=0; i!=val.size(); i++) {    // сумма длин каждого вида трубы 
        sum.push_back(val[i]*v[i]);
    }
    cout<<endl;
    double s=0;
    for(vector<double>::iterator i=sum.begin(); i!=sum.end(); i++) {     // вся длинна которая нужна для труб 
        s+=*i;
        cout<<*i<<" ";
    }
    int kol=ceil(s/zagotovka);    // количество заготовок, длина которая нужна делится на длину заготовки, округляется до большего, ессли ровного количества не хватит
    double ost=((kol*zagotovka)-s)-((val.size()-1)*raz); // отход с вычетом длины реза 
    double m=zagotovka; // отсюда отпиливаем
    double g=0; // столько отпиливаем
    int coo=0; // счётчик
    cout<<endl;
    for(int i=0; i<kol; i++) {
        do {
            vector<double>::iterator it=min_element(sum.begin(),sum.end());
            g+=*it;
            for(int i=0; i<val.size(); i++)
                if(val[i]*v[i]==*it) {
                    cout<<val[i]<<" Дюйма "<<v[i]<<" штуки"<<endl;     // выводим оптимальный вариант 
                    cout<<endl;
                }
            sum.erase(it);
            m-=g;
            coo++;
        } while(m>0 && g<zagotovka);
    }
    cout<<endl;
    cout<<"Заготовок нужно: "<<kol<<endl;
    cout<<"Отход: "<<ost<<endl;
    return 0;
}
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
24.07.2016, 23:56  [ТС]     Программа по резке труб #8
Peoples, Спасибо большое,потсетирую,потом отпишусь о результате
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
25.07.2016, 14:49     Программа по резке труб #9
Hevzy86, на самом деле результат еще зависит от количества тележек, которые вы собираетесь изготовить. А об этом у вас вообще не упомянуто. Или имеется в виду серийное производство?
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6160 / 2889 / 282
Регистрация: 04.12.2011
Сообщений: 7,689
Записей в блоге: 3
25.07.2016, 15:09     Программа по резке труб #10
Цитата Сообщение от Hevzy86 Посмотреть сообщение
IGPIGP,можно и так попробовать,как вы говорите
Я говорил не обдумав как следует:
Цитата Сообщение от IGPIGP Посмотреть сообщение
При такой постановке это вполне рутинная задача.
Пока подавив в пермутациях (перестановках) копии и реверсивные копии, удалось значительно снизить количество вариантов (от N! ),
но всё едино программа получилась очень чувствительна к количеству частей (особенно различных частей). Установив стек 4M в течении 10-ти минут (точнее не мерял) получаю
три заготовки:
40, 40, 42, 42, 52.5, 70 (286.5 в дет. +0.9 рез = 287.4)
45, 45, 52.5, 70, 70 (282.5 в дет + 0.72 рез = 283.22)
40 (40.18)
Это при вводе для 288/0,18 (заготовка/рез)
и наборе выходных деталей:
3X40,
2X45,
2X42,
3X70,
2X52.5

5 разновидностей деталей общим количеством 12 шт. Общее количестао перестановок 12!=479,001,600, но с учётом некоторой (вышеописанной) оптимизации, удалось оставить только 831600, то есть в 576 раз сократить. Иначе не времени ни стека не хватило бы.
Я решал на скорую руку и методом грубой силы, да и не математик я. Думаю тут требуется более изощрённое матобеспечение, логика и... многопоточность. Кроме всего, применение float, - слишком уж большая роскошь и имеет смыл переходить к челоцисленным вычислениям.
Поскольку 4-х значащих цифр тут вполне хватает то Uint16 должно хватить для отображения входных параметров. Тогда должно быть легче т.к. оно вдвое короче чем float.
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
27.07.2016, 00:51  [ТС]     Программа по резке труб #11
Mr.X, их может быть несколько(но не серийное производство)

Добавлено через 7 минут
IGPIGP, спасибо большое за помощь, так то да, быстродействие оч. сильно зависит от кол-ва частей. А можно попросить новый код(который с оптимизацией,хочу его тоже погонять)? Сегодня будем тестировать с "заказчиком" на реальных примерах, я потом отпишусь.

P.S. извиняюсь, что так долго не выходил на связь, основной работы было много
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6160 / 2889 / 282
Регистрация: 04.12.2011
Сообщений: 7,689
Записей в блоге: 3
27.07.2016, 09:12     Программа по резке труб #12
Цитата Сообщение от Hevzy86 Посмотреть сообщение
IGPIGP, спасибо большое за помощь, так то да, быстродействие оч. сильно зависит от кол-ва частей.
Не за что. Мне было интересно порешать задачку, которая так простенько формулируется и внешне выглядит так буднично, как покраска водосточной трубы. А суть достаточно непроста. Тут недавно как раз пришлось встретить противоположность. Несложная задача, невозможная в жизни и очень претенциозно сформулированная. Ну я там и высказался:
Не могу разобраться с алгоритмом деления романа на отдельные тома
Неясно лишь вот что:
Цитата Сообщение от Hevzy86 Посмотреть сообщение
помогите, пожалуйста, решить задачу (друг попросил написать программу,а сам осилить не могу). Парень работает в фирме, которая изготавливает двери для лифтов.
Почему же программист не увидел сложности вычислений и не обосновал сокращения ТЗ?
Цитата Сообщение от Hevzy86 Посмотреть сообщение
А можно попросить новый код(который с оптимизацией,хочу его тоже погонять)?
Его нужно подчистить. А главное, он не решает задачу. Достаточно приличный комп не осиливает программу с 13 деталями из 5-ти разновидностей. Так что 12/5 и всё, а это не укладывается в ТЗ, ведь там 22/6(!).
Да и не программист я. По образованию. Будет странно если мой код сойдёт программисту "за отмазку". И я нос задеру. Я себя знаю. В сомнениях я весь, короче.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,120
Записей в блоге: 2
27.07.2016, 16:58     Программа по резке труб #13
IGPIGP, есть простейший жадный алгоритм, который в общем случае может не гарантировать оптимальность по какому-либо критерию, но в данном случае имхо устроит ТС и его заказчика на все 100, и будет работать очень быстро для большого количества данных. Реализовывать не хочу, чтобы не помогать халявщику зарабатывать чужими руками и мозгами. Суть - берем первую трубу (или обрезок - если на складе есть остатки обрезков с прошлого раза) и имея требуемые размеры деталей с их количеством, честно и оптимальным образом выбираем ее заполнение деталями - чтобы остаток был минимален. Потом берем вторую трубу/обрезок и т.д. пока детали не кончатся.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6160 / 2889 / 282
Регистрация: 04.12.2011
Сообщений: 7,689
Записей в блоге: 3
27.07.2016, 18:11     Программа по резке труб #14
Цитата Сообщение от _Ivana Посмотреть сообщение
IGPIGP, есть простейший жадный алгоритм,
_Ivana, компромиссных стратегий может быть много. Но они не гарантируют наиболее оптимального результата. Мне в моей реализации пока мешает невозможность вызвать перестановку по её номеру. Нужно все перебрать (выбраковывая кучу ненужных), пока не дойдёшь до нужного номера. Просто хочется самому сесть и накатать void permutation<T>(it_beg, it_end, size_t perm_number)
А из стратегий можно бы применить и такую: сортируем по убыванию и выбираем с головы пока не поместится. Непоместившийся возвращаем и берём следующий. Пока не заполним заготовку. С каждой заготовкой голова остатка должна мельчать и манёвренность при заполнении больше. Так рюкзаки наполнять легче всего когда есть гора снаряжения всякого.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,120
Записей в блоге: 2
27.07.2016, 21:32     Программа по резке труб #15
IGPIGP, тогда сразу выплывает несколько вопросов

1) а нужен ли гарантированно оптимальный алгоритм, если он будет делать полный перебор (после всех возможных предварительных отсечений) и будет экспоненциальной сложности? Т.е. добавление одной заготовки увеличит время расчета в 2 раза, и при паре десятков он будет считаться часами? Народ поэтому и придумывает всякие отжиги/муравьев/генетические/жадные и т.п., которые не дают 100% гарантии оптимальности, но дают 99.9....%, а считаются за разумное время. Мне кажется, бизнесмен по постройке лифтов переживет мизерную вероятность неоптимальности

2) по поводу оптимальности, раз уж мы о ней так печемся вот допустим остаток 40 единиц. Что оптимальнее - 10+10+10+10 или 19+7+7+7? Второй вариант, говорите? Хорошо, а 19+7+7+7 и 19+9+6+6? Снова второй? А 19+9+6+6 и 19+9+8+4? Если продолжать, то мы упремся как раз в мой жадный алгоритм, написанный постом выше, гарантирующий минимум каждого следующего остатка, но не гарантирующий общий суммарный минимум (вот такой каламбурчик, да). А ваш критерий максимума максимального остатка не различает все варианты с девятнашками, так что критерий оптимальности придется формализовать строже. И это еще мы не рассматриваем входящие обрезки в качестве исходных труб, а считаем, что у нас всегда только полные новые трубы.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6160 / 2889 / 282
Регистрация: 04.12.2011
Сообщений: 7,689
Записей в блоге: 3
27.07.2016, 22:21     Программа по резке труб #16
Цитата Сообщение от _Ivana Посмотреть сообщение
по поводу оптимальности, раз уж мы о ней так печемся вот допустим остаток 40 единиц. Что оптимальнее - 10+10+10+10 или 19+7+7+7? Второй вариант, говорите?
Извини _Ivana, но не понял ни шиша.
Остаток это что?
Сумма вроде 10+10+10+10 Это что?
Если остаток, это объём под порезку, а сумма, - вариант набора выходных деталей от порезки данного объёма, то все варианты равноценны, так как количество материала деталей, равно количеству исходного. И всё бы хорошо если бы знать, что всё сойдётся. Но жизнь как раз против и где-то в конце будет незаполненная заготовка. Вот почему (мне кажется, но я не уверен), выбор крупных деталей вначале, позволит наиболее плотно заполнять последние (особенно последнюю) заготовки. По аналогии того, что более мелкий материал имеет большую насыпную плотность (при равной физической). И это позволяет надеяться, что "выдавливание" отхода в последнюю заготовку будет статистически достаточно успешно. Доказать это не берусь.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,120
Записей в блоге: 2
27.07.2016, 22:28     Программа по резке труб #17
Цитата Сообщение от IGPIGP Посмотреть сообщение
Остаток это что?
Это остаток обрезков четырех труб после всех распилов. Например, нам требуется напилить в обще сумме 160 единиц и нужны 4 трубы по 50 единиц - будет 4 обрезка суммарной длиной 40 единиц (бредовое ограничение на ширину распила не учитываем - оно непринципиально). Вот, собственно, вся речь об оптимальности - как мы хотим распределить эти суммарные 40 единиц обрезков по 4 обрезкам, и какое их распределение считать предпочтительным и оптимальным.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6160 / 2889 / 282
Регистрация: 04.12.2011
Сообщений: 7,689
Записей в блоге: 3
27.07.2016, 23:33     Программа по резке труб #18
Цитата Сообщение от _Ivana Посмотреть сообщение
как мы хотим распределить эти суммарные 40 единиц обрезков по 4 обрезкам
Всё должно быть в одном куске. В идеале.
Мне программка выдаёт практически полное заполнение всех заготовок кроме одной. Что и требуется.
vlisp
287 / 256 / 38
Регистрация: 10.08.2015
Сообщений: 617
Завершенные тесты: 1
28.07.2016, 00:11     Программа по резке труб #19
https://www.yandex.ua/yandsearch?rdr...t=1469653851.2
Hevzy86
0 / 0 / 0
Регистрация: 24.07.2016
Сообщений: 22
30.07.2016, 19:48  [ТС]     Программа по резке труб #20
_Ivana,ну не то что халявщик, я не лентяй, просто знаний не хватает,как сделать(я пока только учусь,а программа нужна уже сейчас). Но все равно спасибо за помощь Я сегодня покопаюсь в алгоритме(постараюсь понять что к чему), разберу его и полноценно включусь в дискуссию

Добавлено через 5 минут
Доброе время суток, IGPIGP, программа работает(особенно мне понравилась скорость) я сегодня еще покопаюсь в коде (возможно будет пара вопросов по алгоритму) Спасибо за помощь

Добавлено через 8 минут
_Ivana, насчет вашего алгоритма: он интересен, но, как мне кажется,это метод простого перебора всех вариаций для каждой трубы, так? Если да,то он будет медленно работать(при добавлении каждой новой трубы количество вариантов,которых надо перебрать увеличивается в десятки раз, если я не ошибаюсь). Или там есть какая-то фишка?
Yandex
Объявления
30.07.2016, 19:48     Программа по резке труб
Ответ Создать тему
Опции темы

Текущее время: 03:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru