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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.76
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
09.04.2012, 21:08     Жадный алгоритм #1
Суть задачи - имеется 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2012, 21:08     Жадный алгоритм
Посмотрите здесь:

C++ c++/алгоритм
Жадный алгоритм C++
Жадный алгоритм для определения последовательности обхода городов. C++
алгоритм C++
Алгоритм C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
09.04.2012, 21:18     Жадный алгоритм #2
Что-то я не вижу у тебя массива ящиков.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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 и уже в два ящика не уложиться.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.04.2012, 21:47     Жадный алгоритм #4
может поможет
http://en.wikipedia.org/wiki/Bin_packing_problem

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

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


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


Цитата Сообщение от valeriikozlov Посмотреть сообщение
во-вторых, эту задачу жадным алгоритмом ешать нельзя.
у меня условие решить именно жадным алгоритмом
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
09.04.2012, 23:49     Жадный алгоритм #6
Цитата Сообщение от iomika Посмотреть сообщение
ящики считались не в массиве, там просто счетчик.
А как ты тогда собираешься проверять первый ящик? Например, у тебя 4 предмета: 8, 5, 5 и 2. Ты берёшь 8 в первый ящик. Потому берёшь 5 и по твоему алгоритму оно его запихивает во второй ящик, а про первый вообще забывает. Потом берёт вторую 5 и запихивает во второй ящик. Берёт 2 и т.к. первый ящик вообще не сохранён, оно запихивает эту двойку в третий ящик.
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
10.04.2012, 10:50  [ТС]     Жадный алгоритм #7
Цитата Сообщение от Nekto Посмотреть сообщение
А как ты тогда собираешься проверять первый ящик? Например, у тебя 4 предмета: 8, 5, 5 и 2. Ты берёшь 8 в первый ящик. Потому берёшь 5 и по твоему алгоритму оно его запихивает во второй ящик, а про первый вообще забывает. Потом берёт вторую 5 и запихивает во второй ящик. Берёт 2 и т.к. первый ящик вообще не сохранён, оно запихивает эту двойку в третий ящик.
я знаю что ящики считаются не так) написала же что алгоритм работает неправильно. не могу его переписать как надо
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
16.04.2012, 19:02  [ТС]     Жадный алгоритм #8
тема закрыта, алгоритм написан.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
17.04.2012, 14:26     Жадный алгоритм #9
iomika, выложите решение сюда, оно может быть интересно не только вам.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2012, 23:37     Жадный алгоритм
Еще ссылки по теме:

C++ Жадный алгоритм на графе
Жадный граф/алгоритм C++
C++ Жадный алгоритм С++

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

Или воспользуйтесь поиском по форуму:
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;
}
Yandex
Объявления
21.04.2012, 23:37     Жадный алгоритм
Ответ Создать тему
Опции темы

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