Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Евгений2395
0 / 0 / 9
Регистрация: 23.11.2014
Сообщений: 20
Записей в блоге: 2
#1

Задача про рюкзак - ускорить работу программы - C++

08.05.2015, 23:14. Просмотров 469. Ответов 2
Метки нет (Все метки)

Вообщем есть алгоритм, который работает правильно за O(N*W), поэтому при больших значениях будет очень долго считать, нужно изменить так, чтобы при больших значениях считал минуты за 2-3, я уже не знаю что еще делать, плиз хелп
Вот алг.:
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
#include <fstream>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>
#include <iterator>
using namespace std;
int rukzak(const vector<int>& weight, const vector<int>& cost, int W);
int main(int argc, char *argv[])
{
    string s;
    cin >>s;
    ifstream input(s/*argv[1]*/);
    int W,n;
    input>> W >> n;
    vector<int>cost(n);
    vector<int>weight(n);
    //-----------------------zapolnenie------
        for (int i=0;i<n;i++)
        {
            input>>cost[i];
            input>>weight[i];
        }
        //copy(weight.begin(),weight.end(), ostream_iterator<int>(cout, " "));
    //-----------------------------------------------------------
    int vivod=rukzak(weight,cost,W);
    ofstream output;
    output.open("output.txt");
    output<< vivod;
    input.close();
    output.close();
    system("pause");
    return 0;
}
 
int rukzak(const vector<int>& weight, const vector<int>& cost, int W)
{
    int n = weight.size();
    vector<vector<int>>dp(W+1,vector<int>(n+1,0));
    for (int j=1;j<=n;j++)
    {
        for (int w=1;w<=W;w++)
        {
            if (weight[j-1]<=w)
            {
                dp[w][j]=max(dp[w][j-1], dp[w-weight[j-1]][j-1]+cost[j-1]);
            }
            else
            {
                dp[w][j]=dp[w][j-1];
            }
        }
    }
    return dp[W][n];
}
Вот входящий файл:
http://www.cyberforum.ru/cpp-beginners/thread866581.html
0
Вложения
Тип файла: txt input_500.txt (6.2 Кб, 11 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.05.2015, 23:14
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача про рюкзак - ускорить работу программы (C++):

Задача про рюкзак
Всем привет! Есть программа, которая решает задачу про рюкзак. Когда у меня...

Ускорить работу программы
Лексикографический порядок чисел (Время: 1 сек. Память: 16 Мб Сложность:...

Подскажите пожалуйста как ускорить работу программы!
Есть задача :&quot;Во входном файле (вы можете читать данные из файла input.txt)...

Динамический массив, много циклов и простые числа. Как ускорить работу программы ?
Всем привет. Задание следующее: Кто нибудь вводит с клавиатуры число n и k,...

Задача о камнях (почти рюкзак) модификация)
из камней весом p1, p2 ... pn набрать вес W если это возможно вывести yes, если...

2
Dimension
Dimension
573 / 442 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
09.05.2015, 10:19 #2
это задачу быстрее чем за o(n*w) не решить
0
nonedark2008
1022 / 762 / 210
Регистрация: 28.07.2012
Сообщений: 2,118
09.05.2015, 14:47 #3
Цитата Сообщение от Евгений2395 Посмотреть сообщение
я уже не знаю что еще делать
1. Компилируй программу в режиме Release, а не Debug, если ты это еще не сделал.
2. Выкинь вектора и используй обычные массивы.
3. Основную функцию можно распараллелить. omp в помощь.
4. Воспользуйся анализатором производительности на подобии Intel Amplifier, который позволит найти "слабые" участки в коде.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2015, 14:47
Привет! Вот еще темы с решениями:

Ускорить работу функций
Здравствуйте. Не подскажете как можно ускорить работу функций в цикле? А то...

Как ускорить работу?
Прога ещё не доработана, сейчас интересует именно графический режим, когда...

Как ускорить работу с файлами?
Предполагается, что программа будет работать с файлами размера 300-500МБ. Эти...

Как ускорить работу (поиск вхождений подстроки)?
//подсчет kf int NumberKF(string &amp;P, vector&lt;string&gt; &amp; F, const int f){ int...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru