Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/40: Рейтинг темы: голосов - 40, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
1

Задача о рюкзаке методом динамического программирования

03.01.2019, 13:18. Просмотров 7146. Ответов 13
Метки нет (Все метки)

Здравствуйте, помогите, пожалуйста, реализовать до конца программу.
Входные данные должны быть следующими:
Данные подаются на стандартный поток ввода. Пустые строки игнорируются.
Первая строка содержит натуральное число - максимальную массу предметов, которую выдержит рюкзак.
Каждая последующая содержит два неотрицательных числа: массу предмета и его стоимость.

Выходные:
Первая строка содержит два числа: суммарную массу предметов и их суммарную стоимость.
В последующих строках записаны номера предметов, которые были помещены в рюкзак, в порядке возрастания номера.
Результат работы программы выводится в стандартный поток вывода.


Входные данные я реализовал, а вот с выходными проблема. Не понимаю как выводить номера элементов, вошедшие в рюкзак.

Прикладываю код (VS2017):
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
72
73
#include "pch.h"
#include <iostream>
#include <fstream>  
 
using namespace std;
 
int  wts[100], cost[100];
int *x = new int[100000];
int Sum_C = 0, Sum_W = 0, resW = 0, resC = 0;
int W;
int N = 1;
 
void print()
{
    int i;
 
    for (i = 1; i <= N; i++)
    {
        Sum_W = Sum_W + wts[x[i]];
        Sum_C = Sum_C + cost[x[i]];
 
        if (Sum_W <= W && Sum_C > resC) {
            resW = Sum_W;
            resC = Sum_C;
        }
    }
    Sum_C = 0;
    Sum_W = 0;
}
 
void Generate(int n, int k)
{
    int i, j, p;
    for (i = 1; i <= k; i++) x[i] = i;
    print();
    do
    {
        p = 0;
        for (i = k; i >= 1; i--)
            if (x[i] < n - k + i) { p = i; break; }
        if (p > 0)
        {
            x[p]++;
            for (i = p + 1; i <= k; i++) x[i] = x[i - 1] + 1;
            print();
        }
    } while (p > 0);
}
 
int main()
{
    int i = 1;
 
    cin >> W;
 
    while (!std::cin.eof())
    {
        cin >> wts[i];
        cin >> cost[i];
        i++;
    }
 
    while (N <= W)
    {
        Generate(W, N);
        N++;
    }
 
    cout << resW << " " << resC << endl;
 
    system("pause");
    return 0;
}
Добавлено через 32 минуты
И еще, у меня не корректно работает алгоритм "засовывания" в рюкзак:
на данных
165
23 92
31 57
29 49
44 68
53 60
38 43
63 67
85 84
89 87
82 72

Результат вообще не выводится.

Можете, хотя бы направить в каком направлении думать...
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.01.2019, 13:18
Ответы с готовыми решениями:

Задача коммивояжера методом динамического программирования
Помогите пожалуйста переделать коммивояжера методом динамического программирования. Пусть n - это...

Игра Ним методом динамического программирования
добрый день помогите решить задачу методом динамического программирования. Игра Ним с одной кучей...

Задача о рюкзаке методом полного перебора. Нужно пояснение по коду
Здравствуйте, нужно пояснение по этому коду. Код не мой, также в нем много ошибок. Заранее спасибо....

Решение задач динамического программирования методом прямой прогонки
Рассмотреть на любых 2-х примерах. Составить программу на выбор на Pascal,C,C++,C#

13
277 / 203 / 166
Регистрация: 02.05.2017
Сообщений: 812
03.01.2019, 16:00 2
Лучший ответ Сообщение было отмечено BoumRZ как решение

Решение

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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int w,n(0),f,s,max_c(0),max_w(0);
 
int main()
{   
    cin >> w;
    //cin >> n;
    vector<int>weight,cost;
    while(cin >> f >> s){
        ++n;
        weight.push_back(f);
        cost.push_back(s);
    }
    //for(int i = 0;i<n;++i){       
    //  cin >> f >> s;
    //  weight.push_back(f);
    //  cost.push_back(s);
    //}
    int matrix[n+1][w+1];
    for(int i = 0;i<=w;++i)matrix[0][i] = 0;
    for(int i = 0;i<=n;++i)matrix[i][0] = 0;
    for(int i = 1;i<=n;++i){
        for(int j = 1;j<=w;++j)if(weight[i-1] <= j){
            matrix[i][j] = max(matrix[i-1][j],matrix[i-1][j-weight[i-1]] + cost[i-1]);
        } else matrix[i][j] = matrix[i-1][j];
    }
    vector<int>answer;
    for(int i = n;;){
        for(int j = w;;){
            if(!matrix[i][j])break;
            if(matrix[i][j] != matrix[i-1][j]){
                answer.push_back(i);
                max_c += cost[i-1];
                max_w += weight[i-1];
                j -= weight[i-1];
            } 
            --i;
        }
        break;
    }
    sort(answer.begin(),answer.end());
    cout << max_w << ' ' << max_c << '\n';
    for(int i = 0;i<answer.size();++i)cout << answer[i] << ' ';
    
    return 0;
}
https://ideone.com/Q8iRjd
1
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
03.01.2019, 16:01  [ТС] 3
Извини, а можешь вкратце объяснить что происходит в этом коде?
0
277 / 203 / 166
Регистрация: 02.05.2017
Сообщений: 812
03.01.2019, 16:02 4
BoumRZ, тут все расписано, мне лень,сорян
http://neerc.ifmo.ru/wiki/inde... 0.B8.D1.8F
0
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
03.01.2019, 16:04  [ТС] 5
LegionK, ладно, в любом случае огромное спасибо. Вы мне очень помогли.
Теперь мне осталось получше разобраться..
0
277 / 203 / 166
Регистрация: 02.05.2017
Сообщений: 812
03.01.2019, 16:05 6
BoumRZ, вы хоть проверьте,чтобы работало, я же тоже накосячить могу
0
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
03.01.2019, 16:13  [ТС] 7
LegionK, на том сайте, который Вы скинули компилируется хорошо. Я проверял: заново компилировал.
А вот в VS почему-то не хочет компилироваться. Пишет, что выражение в индексе матрицы должно быть константным, но при этом, не n, не w нельзя делать константными, иначе изменять их нельзя будет..

Возможно, это баг самой VS, потому что бывает с ней нечто подобное: на других компиляторах компилируется, а на ней -нет.
0
277 / 203 / 166
Регистрация: 02.05.2017
Сообщений: 812
03.01.2019, 16:29 8
BoumRZ, потому что в vs нельзя указать размер массива переменной
https://ideone.com/pqt2eS
За то,что компилироваться будет - я гарантирую,лучше корректность ответа бы проверили
0
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
03.01.2019, 17:36  [ТС] 9
LegionK, Я проверил решение на ejudge и тест показал, что программа не работает на следующих данных:
750000000
70000000 135
73000000 139
77000000 149
80000000 150
82000000 156
87000000 163
90000000 173
94000000 184
98000000 192
106000000 201
110000000 210
113000000 214
115000000 221
118000000 229
120000000 240

Как можно решить эту проблему?
0
277 / 203 / 166
Регистрация: 02.05.2017
Сообщений: 812
03.01.2019, 18:09 10
BoumRZ, и какой вердикт он отдает? Wrong answer/runtime error/time limit /memory limit?
0
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
03.01.2019, 18:12  [ТС] 11
LegionK,Превышено ограничение на время. А пишет "Max. CPU time: 0.612"
0
277 / 203 / 166
Регистрация: 02.05.2017
Сообщений: 812
03.01.2019, 18:22 12
BoumRZ, не, с этим я тебе помочь уже не могу,сорян, даже Вики грит,что w больше 10^7 делать не стоит. Алгоритм же NW сложность имеет, это порядка 15*7,5*10^8 операций. Ну это даже чуть больше,чем, например, максимальные 10^9 для 1 сек в проверяющей системе timus.
Так что извини,но с этим я помочь не могу
0
0 / 0 / 0
Регистрация: 17.12.2018
Сообщений: 20
03.01.2019, 18:50  [ТС] 13
У меня есть идея: найти НОД для весов и на него разделить массы рюкзака и предметов.

Пока подумаю над этой идеей и над её реализацией, а, раз это форум, решил об этом сюда написать, вдруг у кого-то раньше появятся идеи как реализовать)
0
2046 / 1520 / 167
Регистрация: 14.12.2014
Сообщений: 13,326
03.01.2019, 19:14 14
BoumRZ, Ну есть еще вариант использования эвристики вместо брута. Итемы сортируются по невозрастанию веса и впихивается начиная с наибольшего что влезет. Не гарантирует наиболее оптимального решения но приемлемо оптимальное будет за примерно линейное время. Эту эвристику в принципе все системы раскроя заготовок пользуют в реальной жизни.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.01.2019, 19:14

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Задача о рюкзаке методом динамического программирования, исправить код
Помогите разобраться! Написал прогу, которая должна решать задачу о рюкзаке методом Беллмана...

Решение задачи о рюкзаке методом динамического программирования
Разбейте задачу на подзадачи и постройте рекуррентное соотношение для вычисления значений подзадач....

Задача методом динамического программирования
Добрый день. Передо мной стоит решение задачи методом динамического программирования (табличный...

Задача о выборе траектории методом динамического программирования
Необходимо проехать от Киева до Симферополя. Возможны несколько путей (см.сеть). Число,...


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

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

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