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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Защита от ввода букв http://www.cyberforum.ru/cpp-beginners/thread543767.html
Нужно в программу вставить защиту от ввода букв. Что то у меня не получается. (В программе вводится только цифра) #include <iostream.h> #include <conio.h> #include <stdio.h> #include <time.h>...
C++ дешифратор в с++ здраствуйте!скаите пожалуйста как функцию дешифратора реализовать в с++!чтобы при таком то наборе выбирал тот вход который соответствует двоичному коду введенному вначале?заранее спасибо! http://www.cyberforum.ru/cpp-beginners/thread543761.html
Вектор: merge, vector.swap C++
Идея такая: есть вектор 2 половину отсортированы можно сделать inplace_merge, но комбинация merge + выделение памяти под новый вектор работает быстрее, поэтому делаю так { vector<int>...
Упорядоченный массив C++
Здравствуйте, можете помочь с задачей :"Дано целочисленный массив из n элементов, упорядоченный по возрастанию. Добавить в массив целое a, так чтобы новый массив из n +1- го элемента остался...
C++ Кривая Пеано http://www.cyberforum.ru/cpp-beginners/thread543724.html
Доброго времени суток, может кто нибудь подсказать или натолкнуть на мысль, как можно реализовать кривую Пеано на c++ Добавлено через 1 час 49 минут #include <iostream> #include <string> ...
C++ несколько простых вопросов 1) у каждого процесса свою адресное пространство(то есть несколько процессов могут начинаться допустим с адреса 0x401000)? 2) при загрузке dll библиотек ,а также при добавление lib библиотек они... подробнее

Показать сообщение отдельно
iomika
2 / 2 / 0
Регистрация: 12.11.2011
Сообщений: 9

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

09.04.2012, 21:08. Просмотров 5393. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru