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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
allex
0 / 0 / 0
Регистрация: 23.01.2013
Сообщений: 20
#1

упаковка по ящикам - C++

08.10.2013, 23:19. Просмотров 421. Ответов 7
Метки нет (Все метки)

здравствуйте,

помогите пожалуйста с программой, которая будет упаковывать элементы в ящики (определенного размера)
с минимальным занимаемым местом.

например, последовательность элементов:
5,7,3,9,6,8,1,4,2,5 (например хранится в массиве а)
Объем ящиков = 10

шаг 1. в 1 ящик кладется 5 (a[0])
шаг 2. т.к. для a[1] уже нет места в 0 ящике, то во 2 ящик - 7 (a[1])
шаг 3. a[2] предпочтительно класть во второй ящик, т.к. 7+3=10, что совпадает с объемом ящика и туда уже больше ничего не положишь.
и т.д.

у меня получилась упрощенная версия, где отсутствует выбор наиболее подходящего элеента (если объем текущего ящика+текущий элеент<11, то запись элеента в ящик)

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
int main()
{
    int a[15]= {5,7,3,9,6,8,1,4,2,5};
    int b[10]; // 10 ящиков
    int i,j,k,min,t;
    
    for (i=0; i<10; i++) //вывод на экран всех элементов
        {cout<<a[i]<<" ";
        b[i]=0;}
        
    //      b[0]=a[0];
 
    for (i=0; i<10; i++) //для элементов
        {
            for (j=0; j<10; j++) // для ящиков
                {
                    if (b[j]+a[i]<11)
                        {
                            b[j]=b[j]+a[i]; cout<<"\n элемент a"<<i<<" добавлен в ящик b"<<j<<"="<<b[j]; break;
                        }
                                                
                }
        }
        cout<<"\n------------------------\n";
    for (i=0; i<10; i++) //вывод на экран всех ящиков
            {cout<<b[i]<<" ";}
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Leshak
259 / 235 / 40
Регистрация: 10.12.2011
Сообщений: 513
08.10.2013, 23:42     упаковка по ящикам #2
Натолкну вас на эдакую мысль.

9 + 1 = 10 ( max min )
8 + 2 = 10
7 + 3 = 10
6 + 4 = 10
5 + 5 = 10

Массив кстати можна отсротировать для приличия ) И потом разбить его пополам суммируя с конца. Ну концовку 5+5 додумайте уже сами )
Влом за вас реализацию писать
allex
0 / 0 / 0
Регистрация: 23.01.2013
Сообщений: 20
08.10.2013, 23:52  [ТС]     упаковка по ящикам #3
нет, нужно упаковывать без сортировки. такая задача )))
Leshak
259 / 235 / 40
Регистрация: 10.12.2011
Сообщений: 513
09.10.2013, 00:02     упаковка по ящикам #4
Ну, а кто тогда к примеру мешает завести булевый массив который на каждом шаге будет сверять, был ли у вас уже такой мин и макс или не было. Решение вашей проблемы через всеми любимое место
При этом можна сделать один внешний цикл, и один вложенный на проверку внутри.
allex
0 / 0 / 0
Регистрация: 23.01.2013
Сообщений: 20
09.10.2013, 00:07  [ТС]     упаковка по ящикам #5
не совсем понял что вы имеете ввиду ))
вот что у меня пока получается, но с ошибками. вы про это рассказывали?

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
int main()
{
    int a[15]= {5,7,3,9,6,8,1,4,2,5};
    int b[10]; // 10 ящиков
    int i,j,k,min,t;
    
    for (i=0; i<10; i++) //вывод на экран всех элементов
        {cout<<a[i]<<" ";
        b[i]=0;}
        
    b[0]=a[0];
 
    for (i=1; i<10; i++) //для элементов
        {
            for (j=0; j<10; j++) // для ящиков
                {
                    if (b[j]+a[i]<11)
                        { t=0; // для хранения счетчика min пары
                            for (k=0;k<10;k++) // поиск пары ящ+эл=макс, но были в границе 11
                            {
                                if ((10-(b[k]+a[i]))>0) min=10-(b[k]+a[i]); t++;                            
                            }
                            b[t]=a[i]; cout<<"\n элемент a"<<i<<"="<<a[i]<<" добавлен в ящик b"<<j<<"="<<b[j]; break;
                        }
                                
                }
        }
        cout<<"\n------------------------\n";
    for (i=0; i<10; i++) //вывод на экран всех ящиков
            {cout<<b[i]<<" ";}
}
Leshak
259 / 235 / 40
Регистрация: 10.12.2011
Сообщений: 513
09.10.2013, 00:23     упаковка по ящикам #6
Ясно, что такое bool array мы и знать не знаем =)
Я это имел ввиду

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int Max = 10;
bool IfThereWasAPair[Max] = {false}; /*если так массив не заполнится заполняйте по примеру ниже*/
int a[] = { /*ваши значения*/ }
int b[Max]; 
int min, max, count(0);
 
for ( int i = 0 ; i < Max ; i++ ) IfThereWasAPair[i] = false;
 
/* внешний цикл ...*/
     for ( int i = 0 ; i < Max ; i++)
          {
              if ( min < a[i]  & IfThereWasAPair[i] == false )  min = a[i]; else IfThereWasAPair[i] = true;
             /* находим максимум...*/
             /* заносим сумму max + min в массив...*/
          }
allex
0 / 0 / 0
Регистрация: 23.01.2013
Сообщений: 20
09.10.2013, 00:39  [ТС]     упаковка по ящикам #7
не знаю, может я чего не понял в вашем коде,
но искать максимумы не нужно...

нужно находить в процессе решения наиболее оптимальную комбинацию элемента и ящика.
например,
в 1 ящик кладется 5 (a[0])
во 2 ящик - 7 (a[1])
во 2 ящик добавляется 3
и т.д.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2013, 00:58     упаковка по ящикам
Еще ссылки по теме:

C++ Упаковка бинарного дерева в массив
C++ Упаковка std :: vector <bool> в байты
C++ Упаковка/распаковка стороннего файла в exe
C++ Упаковка пакета с помощью операции сдвига
Упаковка строки с шестнадцатиричными значениями C++

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

Или воспользуйтесь поиском по форуму:
Leshak
259 / 235 / 40
Регистрация: 10.12.2011
Сообщений: 513
09.10.2013, 00:58     упаковка по ящикам #8
Хорошо, что тогда является наиболее оптимальным вариантом?
сразу кину два контр примера:
1+4+3+2 = 10 - не оптимально ?
5+4+1 = 10 - не оптимально ?
( вопрос, куда девать остальные коробки ? )При первом варианте вы упаковываете все коробки ( 2 пост ).

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

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

П.с. писать за вас программу, увольте
Yandex
Объявления
09.10.2013, 00:58     упаковка по ящикам
Ответ Создать тему
Опции темы

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