Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
4 / 4 / 0
Регистрация: 07.03.2019
Сообщений: 249

Жадный алгоритм Рюкзака

16.06.2024, 15:21. Показов 1956. Ответов 20
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Подскажите, пожалуйста.

На просторах интернета пытался найти жадный алгоритм рюкзака для своей задачи. Нашел реализацию на С++ с помощью векторов:

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
#include <iostream>
#include <vector>
#include <algorithm>
 
 
int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
    {
        size_t n = wts.size();
        std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n+1, 0));
        for (size_t j = 1; j <= n; j++)
        {
            for (int w = 1; w <= W; w++)
            {
                if (wts[j-1] <= w)
                {
                    dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
                }
                else
                {
                    dp[w][j] = dp[w][j - 1];
                }
            }
        }
        return dp[W][n];
    }
      
 
int main()
{
    int n, m, v, g, ro, summa_m = 0, summa_v = 0, W;
    
    std::vector<int> OK;
    std::vector<int> Mass;
    
    std::cin >> n;
    std::cin >> g;
    std::cin >> ro;
    
    
    for (int i=0;i<n;i++)
    {
        std::cin >> m;
        std::cin >> v;
        if (ro*v >= m)
        {
            summa_m+=m;
            summa_v+=v;
        }
        else
        {
            OK.push_back((m-ro*v));
            Mass.push_back(m);
        }
    }
    W = ro*summa_v - summa_m;
    
    
    std::cout << summa_m + knapsack2(OK, Mass, W);
 
    return 0;
}
Что делает данная программа.

На вход подается: n - количество камней, g - ускорение свободного падения, ro - плотность жидкости.
Далее по циклу задаются сами камни: m - их масса и v - объем.

Нужно найти максимальную массу камней (подразумевается, что мы можем превратить камни в некий монолит), которая будет плавать (т.е. ro*g*v >= m*g). Понятно, что g можно сократить и по ходу задачи оно нигде использоваться не будет, то по условию его нужно ввести.

В начале мы складываем все камни, которые сами по себе будут плавать -> их суммарная монолитная масса тоже будет плавать.

А далее по алгоритму рюкзака добираем "толстые" камни с максимально возможной массой.

Проблема в том, что данный алгоритм не оптимизирован по объему памяти. Можно ли как-нибудь оптимизировать данный код?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.06.2024, 15:21
Ответы с готовыми решениями:

Как работает алгоритм ПП рюкзака?
Здравствуйте, вот код полного перебора рюкзака. Все понимаю, кроме главного цикла, где всё высчитывается. v - объем рюкзака, n -кол- во...

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

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

20
19.06.2024, 00:39
Студворк — интернет-сервис помощи студентам

Не по теме:

"А що замість той ноги у нього було.
Про це Ніколи не дізнається ні хто."

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.06.2024, 00:39

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru