2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
1

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

09.04.2012, 21:08. Показов 17370. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.04.2012, 21:08
Ответы с готовыми решениями:

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

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

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

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

9
347 / 292 / 37
Регистрация: 23.03.2012
Сообщений: 838
09.04.2012, 21:18 2
Что-то я не вижу у тебя массива ящиков.
0
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
09.04.2012, 21:24 3
во-первых, код не соответствует написанному алгоритму.
во-вторых, эту задачу жадным алгоритмом ешать нельзя. Вот пример:
имеется два ящика объемом каждый по 10. Имеются предметы (уже отсортированные по убыванию):
5 4 4 3 2 2
Минимальное количество необходимых ящиков 2 шт. Расклад выглядит таким:
5 3 2
4 4 2
Но следуя Вашему жадному алгоритму в первый ящик попадут сначало 5, потом 4 и уже в два ящика не уложиться.
0
3972 / 3243 / 907
Регистрация: 25.03.2012
Сообщений: 12,063
Записей в блоге: 1
09.04.2012, 21:47 4
может поможет
http://en.wikipedia.org/wiki/Bin_packing_problem

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

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


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


Цитата Сообщение от valeriikozlov Посмотреть сообщение
во-вторых, эту задачу жадным алгоритмом ешать нельзя.
у меня условие решить именно жадным алгоритмом
0
347 / 292 / 37
Регистрация: 23.03.2012
Сообщений: 838
09.04.2012, 23:49 6
Цитата Сообщение от iomika Посмотреть сообщение
ящики считались не в массиве, там просто счетчик.
А как ты тогда собираешься проверять первый ящик? Например, у тебя 4 предмета: 8, 5, 5 и 2. Ты берёшь 8 в первый ящик. Потому берёшь 5 и по твоему алгоритму оно его запихивает во второй ящик, а про первый вообще забывает. Потом берёт вторую 5 и запихивает во второй ящик. Берёт 2 и т.к. первый ящик вообще не сохранён, оно запихивает эту двойку в третий ящик.
0
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
10.04.2012, 10:50  [ТС] 7
Цитата Сообщение от Nekto Посмотреть сообщение
А как ты тогда собираешься проверять первый ящик? Например, у тебя 4 предмета: 8, 5, 5 и 2. Ты берёшь 8 в первый ящик. Потому берёшь 5 и по твоему алгоритму оно его запихивает во второй ящик, а про первый вообще забывает. Потом берёт вторую 5 и запихивает во второй ящик. Берёт 2 и т.к. первый ящик вообще не сохранён, оно запихивает эту двойку в третий ящик.
я знаю что ящики считаются не так) написала же что алгоритм работает неправильно. не могу его переписать как надо
0
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9
16.04.2012, 19:02  [ТС] 8
тема закрыта, алгоритм написан.
0
Эксперт С++
5052 / 3113 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
17.04.2012, 14:26 9
iomika, выложите решение сюда, оно может быть интересно не только вам.
0
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.04.2012, 23:37
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru