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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.76
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
#1

Жадный алгоритм - C++

09.04.2012, 21:08. Просмотров 5159. Ответов 9
Метки нет (Все метки)

Суть задачи - имеется N предметов различного размера. Один ящик имеет строгую вместимость. Необходимо разложить все N предметов в минимальное количество ящиков.
Не получается написать алгоритм разложения по ящикам. Он должен выглядеть так - сортируем предметы по уменьшению веса. Берем первый предмет и ложим в ящик. Берем второй предмет, проверяем вмещается ли он в первый ящик, если нет ложим во второй. Берем третий предмет проверяем вмещается ли в 1 ящик, если нет вмещается ли во второй, если нет ложим в третий ящик и тд.
Вот рабочий код, но подсчет ящиков ведется неправильно!

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
67
68
#include <stdio.h>
#include <conio.h>
#include <iostream>
 
int main()
{
    setlocale (LC_ALL, "Russian");
    //======= Задание массива =======//
    const int n = 10;
    int i, a[n], box=0, c=0, kol=1, tmp;
 
    printf("Введите вес предметов\n");
    for ( i = 0; i < n; i ++ ) 
    {
        printf("(%d)---> ", i );
        scanf ("%d", &a[i]);
    }
 
    //====== СОРТИРОВКА ПО УБЫВАНИЮ ========//
 
    for(int i = 0; i < n - 1; ++i) // i - номер прохода
    {            
        for(int j = 0; j < n - 1; ++j) // внутренний цикл прохода
        {    
            if (a[j + 1] > a[j])
            {
                tmp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = tmp;
            }
        }
    }
    //======== Вывод массива на экран ===========//
    printf("\nСортировка по убыванию:\n");
    for ( i = 0; i < n; i ++ )
        printf("%d ", a[i]);
 
    //======== Подсчет ящиков ==================//
    //for (int i=c; i < n; i++)
    while (c != n)
    {
        box=box+a[c];
 
 
        if (box <10)
        {   
            c++;
        }
        if (box > 10)
        {
 
            kol++;
            box=0;
        }
        if (box == 10)
        {
            c++;
            kol++;
            box=0;
        }
 
 
    }
 
    printf("\nКоличество ящиков =  %d", kol);
    getch();
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2012, 21:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Жадный алгоритм (C++):

Жадный алгоритм С++ - C++
С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну операцию объединяются 2 счета и банк...

Жадный алгоритм - C++
Добрый день. Помогите, пожалуйста, понять, где затаилась ошибка. Это задачка на жадный алгоритм: пользователь вводит размер...

Жадный алгоритм - C++
Задача: По следам олимпиады. Известно, что оптимальным выбором лыж является такой, когда длина лыж максимально приближена к высоте...

Жадный алгоритм - C++
Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно правильное. Кто знает? вот вполне рабочий...

Жадный алгоритм на графе - C++
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть, дан ориентированный взвешенный граф (можно...

Жадный алгоритм (рюкзак) - C++
слишком медленно, но верно работает программа. Помогите пожалуйста ускорить. (извиняюсь за транслит или что-то похожее на него) ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
09.04.2012, 21:18 #2
Что-то я не вижу у тебя массива ящиков.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.04.2012, 21:24 #3
во-первых, код не соответствует написанному алгоритму.
во-вторых, эту задачу жадным алгоритмом ешать нельзя. Вот пример:
имеется два ящика объемом каждый по 10. Имеются предметы (уже отсортированные по убыванию):
5 4 4 3 2 2
Минимальное количество необходимых ящиков 2 шт. Расклад выглядит таким:
5 3 2
4 4 2
Но следуя Вашему жадному алгоритму в первый ящик попадут сначало 5, потом 4 и уже в два ящика не уложиться.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
09.04.2012, 21:47 #4
может поможет
http://en.wikipedia.org/wiki/Bin_packing_problem

А то сортировать и запихивать по порядку не самый оптимальный метод

Добавлено через 21 минуту
копай в сторону "метода динамического программирования"
Я читал про него в книге Окулова
0
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
09.04.2012, 22:42  [ТС] #5
Цитата Сообщение от Nekto Посмотреть сообщение
Что-то я не вижу у тебя массива ящиков.
ящики считались не в массиве, там просто счетчик.


Цитата Сообщение от valeriikozlov Посмотреть сообщение
во-первых, код не соответствует написанному алгоритму
написала ведь, что считается неправильно


Цитата Сообщение от valeriikozlov Посмотреть сообщение
во-вторых, эту задачу жадным алгоритмом ешать нельзя.
у меня условие решить именно жадным алгоритмом
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
09.04.2012, 23:49 #6
Цитата Сообщение от iomika Посмотреть сообщение
ящики считались не в массиве, там просто счетчик.
А как ты тогда собираешься проверять первый ящик? Например, у тебя 4 предмета: 8, 5, 5 и 2. Ты берёшь 8 в первый ящик. Потому берёшь 5 и по твоему алгоритму оно его запихивает во второй ящик, а про первый вообще забывает. Потом берёт вторую 5 и запихивает во второй ящик. Берёт 2 и т.к. первый ящик вообще не сохранён, оно запихивает эту двойку в третий ящик.
0
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
10.04.2012, 10:50  [ТС] #7
Цитата Сообщение от Nekto Посмотреть сообщение
А как ты тогда собираешься проверять первый ящик? Например, у тебя 4 предмета: 8, 5, 5 и 2. Ты берёшь 8 в первый ящик. Потому берёшь 5 и по твоему алгоритму оно его запихивает во второй ящик, а про первый вообще забывает. Потом берёт вторую 5 и запихивает во второй ящик. Берёт 2 и т.к. первый ящик вообще не сохранён, оно запихивает эту двойку в третий ящик.
я знаю что ящики считаются не так) написала же что алгоритм работает неправильно. не могу его переписать как надо
0
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
16.04.2012, 19:02  [ТС] #8
тема закрыта, алгоритм написан.
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
17.04.2012, 14:26 #9
iomika, выложите решение сюда, оно может быть интересно не только вам.
0
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
21.04.2012, 23:37  [ТС] #10
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
67
68
69
70
71
#include <stdio.h>
#include <conio.h>
#include <iostream>
 
int main()
{
        setlocale (LC_ALL, "Russian");
        //======= Задание массива =======//
        const int n = 4;
        int i, a[n], b[n], box=0, c=0, kol=0, tmp;
 
        printf("Введите вес предметов\n");
        for ( i = 0; i < n; i ++ ) 
        {
                printf("(%d)---> ", i );
                scanf ("%d", &a[i]);
        }
 
        for (int i = 0; i <n ; i ++)
        {
                b[i] = 0;
        }
 
        //====== СОРТИРОВКА ПО УБЫВАНИЮ ========//
 
        for(int i = 0; i < n - 1; ++i) // i - номер прохода
        {            
                for(int j = 0; j < n - 1; ++j) // внутренний цикл прохода
                {    
                        if (a[j + 1] > a[j])
                        {
                                tmp = a[j + 1];
                                a[j + 1] = a[j];
                                a[j] = tmp;
                        }
                }
        }
        //======== Вывод массива на экран ===========//
        printf("\nСортировка по убыванию:\n");
        for ( i = 0; i < n; i ++ )
                printf("%d ", a[i]);
 
        //======== Подсчет ящиков ==================//
        for (int i=0; i < n; i++)
        {           
 
                for (int j=0; j<n; j++)
                {
                        if (b[j]+a[i] <= 10)
                        {
                                //printf ("\n номер ящика %d", j);
                                b[j]=b[j]+a[i];
                                //printf ("   масса предмета %d", a[i]);
                                break;
                        }
 
                }
        }
 
 
        printf("\n\n Список ящиков:\n");
        for ( i = 0; i < n; i ++ )
                if (b[i] != 0)
                {
                        kol++;
                        printf("%d ", b[i]);
                }
        printf("\n\nСтоимость %d ", kol);
        getch();
        return 0;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2012, 23:37
Привет! Вот еще темы с ответами:

Жадный граф/алгоритм - C++
Требуется написать программу с графическим интерфейсом: пользователь задаёт точки (A, B, C и т.д.). Далее соединяет между собой какие-то...

Жадный алгоритм сортировки массива(динамический) - C++
Здравствуйте, учусь работать с сортировками массивов, в данном случае жадный алгоритм. Алгоритм работы(): Ввод размера массива -&gt;...

Жадный алгоритм нахождения абсолютной разницы чисел - C++
Вот мое задание: А вот мой код: #include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace...

Жадный алгоритм. Оптимальный состав груза специй - C++
Добрый вечер, можете подсказать как в данной задачи использовать Жадный алгоритм? Капитан корабля, остановился на заброшенном острове,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
21.04.2012, 23:37
Ответ Создать тему
Опции темы

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