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

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

10.07.2016, 05:51. Показов 7703. Ответов 8
Метки нет (Все метки)

слишком медленно, но верно работает программа. Помогите пожалуйста ускорить. (извиняюсь за транслит или что-то похожее на него)
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
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
typedef pair <int, int> Tovar;
double rukzak(vector <Tovar> vec, int W)
{
    vector <double> chena;
    double c=0,k;
    for (std::size_t j = 0; j < vec.size(); j++) {
        chena.push_back(vec[j].first / vec[j].second);
    }
    for (std::size_t i = 0; i < chena.size(); i++) {
        for (std::size_t j = i+1; j < chena.size(); j++)
        if (chena[i] < chena[j]) {
            swap(chena[i], chena[j]);
            swap(vec[i],vec[j]);
        }   
    }
    while (W > 0){
        for (std::size_t i = 0; i < chena.size(); i++) {
            
            if ((W - vec[i].second) >= 0)
                k = 1;
            else k = -((W - vec[i].second) / vec[i].second);
            W -=(abs(k)*vec[i].second);
            if (W<0)break;
            c +=(vec[i].first*k);
        }
    } 
    return c;
}
 
int main() {
    int n, W;
    cin >> n;
    cin >> W;
    vector <Tovar> tovar(n);
    for (int i = 0; i < n; i++) {
        std::cin >> tovar[i].first >> tovar[i].second;
    }
    cout << fixed << rukzak(tovar, W);
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.07.2016, 05:51
Ответы с готовыми решениями:

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

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

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

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

8
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
10.07.2016, 07:42 2
Цитата Сообщение от alena_sn Посмотреть сообщение
слишком медленно, но верно работает программа. Помогите пожалуйста ускорить.
А можете сказать на каком тесте и как медленно работает? И до какого значения хотите ускорить?
0
0 / 0 / 0
Регистрация: 09.07.2016
Сообщений: 4
10.07.2016, 10:12  [ТС] 3
Лимит времени 5 секунд, думаю, что проблема в сортировке, но не получается переделать по другому.
0
Эксперт С++
1623 / 953 / 782
Регистрация: 06.02.2016
Сообщений: 2,449
Записей в блоге: 30
10.07.2016, 10:59 4
Так должно меньше времени занимать, попробуйте
C++
1
2
3
4
5
6
7
#include<algorithm>   // для sort
int main(){
... 
// сортировка по возрастанию 
sort(vec.begin(),vec.end());                // если по убыванию, то sort(vec.rbegin(),vec.rend()); 
  sort(chena.begin(),chena.end());
}
0
2549 / 1208 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
10.07.2016, 13:30 5
alena_sn, а можно текстовку задания - что приходит, что должно произойти, что должно быть на выходе
0
0 / 0 / 0
Регистрация: 09.07.2016
Сообщений: 4
10.07.2016, 14:30  [ТС] 6
проблема в том, что вектор из пары, должен сортироваться одновременно с вектором цены, тк сортируется только второй, первый просто должен так же измениться.

Добавлено через 3 минуты
задание такое: на вход принимается количество предметов, вместимость рюкзака. потом заполняется вектор из пар длинны этого количества предметов.(первое это стоимость предмета, второе- его вес) нужно заполнить рюкзак полностью с максимальной стоимостью содержимого. можно брать предметы частями.вернуть стоимость рюкзака

Добавлено через 28 минут
так тоже превышаю лимит в 5 секунд(
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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
 
bool pairCompare(const pair<int, int>& firstElem, const pair<int, int>& secondElem) {
    return firstElem.first / (double)firstElem.second > secondElem.first / (double)secondElem.second;
}
 
typedef std::pair <int, int> Tovar;
double rukzak(vector <Tovar> vec, int W)
{
    double c = 0, k;
    while (W > 0) {
        for (std::size_t i = 0; i < vec.size(); i++) {
 
            if ((W - vec[i].second) >= 0)
                k = 1;
            else k = -((W - vec[i].second) / vec[i].second);
            W -= (abs(k)*vec[i].second);
            if (W<0)break;
            c += (vec[i].first*k);
        }
    }
    return c;
}
 
int main() {
    int n, W;
    cin >> n;
    cin >> W;
    vector <Tovar> tovar(n);
    for (int i = 0; i < n; i++) {
        std::cin >> tovar[i].first >> tovar[i].second;
    }
    sort(tovar.begin(), tovar.end(), pairCompare);
    cout << fixed << rukzak(tovar, W);
    return 0;
}
0
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
10.07.2016, 14:59 7
alena_sn, возможно, в задании написано, что входные значения записаны в определенном файле. Вы же их считываете с со стандартного входа (консоли). Вот поэтому ваша программа ожидает ввода, а его нету, так и проходит 5 секунд.
0
0 / 0 / 0
Регистрация: 09.07.2016
Сообщений: 4
10.07.2016, 15:21  [ТС] 8
Первая строка содержит количество предметов 1≤n≤10^3 и вместимость рюкзака 0≤W≤2⋅10^6. Каждая из следующих n строк задаёт стоимость 0≤ci≤2⋅10^6 и объём 0<wi≤2⋅10^6 предмета (n, W, ci, wi — целые числа). Выведите максимальную стоимость частей предметов (от каждого предмета можно отделить любую часть, стоимость и объём при этом пропорционально уменьшатся), помещающихся в данный рюкзак, с точностью не менее трёх знаков после запятой. (это точная формулировка задания)
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
10.07.2016, 16:28 9
Эта задача уже есть на форуме.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.07.2016, 16:28
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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