Задача рюкзак C++
15 Апр

«Рюкзак»

Имеется рюкзак, вместимость которого W и набор из N предметов, причём i-ый предмет займёт Wi места, если положить его в рюкзак, и имеет ценность Ci. Вашей задачей является собрать в рюкзаке набор предметов, имеющий максимальную суммарную ценность.

Входные данные
На первой строке два целых числа W и N. На каждой из последующих N строк по два целых числа – характеристики очередного предмета Wi и Ci.

Выходные данные
На первой строке выведите два числа C – суммарную ценность выбранных предметов и M – их количество. На следующей строке выведите M чисел – номера выбранных предметов (в исходном наборе они занумерованы начиная с единицы)

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <fstream>
#include <string>
 
class Bacpack {
private:
int **T;
int g, P, n;
int *W, *C;
 
public:
Bacpack() {
g = 1;
 
std::ifstream w("WC.txt");
int temp; //заполнили кол-во предметов
w >> temp;
n = temp;
 
int q, e;     //запомнили веса и стоимости
int i = 0;
W = new int[n]; //вес
C = new int[n]; //стоимость
while (!w.eof()) {
w >> q >> e;
W[i] = q;
C[i] = e;
i++;
}
 
P = W[0]; //заполнили максимальную стоимость
int len_mass = n;
for (int i = 0; i < len_mass; i++) {
P = __max(P, W[i+1]);
}
}
 
int max_vyb() {
T = new int*[P]; //описали матрицу Т
for (int i = 0; i < n; i++) {
T[i] = new int[P];
}
 
for (int j = 0; j < P; j++) { //заполнили матрицу Т 8-ками
for (int i = 0; i < n; i++) {
T[i][j] = 8;
}
}
 
for (int j = 0; j < P; j++) { //обнуление первой строки
T[0][j] = 0;
}
for (int i = 0; i < n; i++) { //обнуление первого столбца
T[i][0] = 0;
}
 
for (int j = 1; j < P; j++) {
for (int i = 1; i < n; i++) {
if (W[i] <= j) {
T[i][j] = __max((T[i - 1][j]), (T[i - 1][j-W[i]] + C[i]));
}
else {
T[i][j] = T[i - 1][j];
}
}
}
return T[n-1][P-1];
}
 
void print_backpack(int i, int j) {
int *mass;
mass = new int[P];
if (T[i][j] == 0) {
std::cout << "\nКол-во: " << g;
std::cout << "\n\n";
system("pause");
exit(1);
}
else {
if (T[i - 1][j] == T[i][j]) {
g++;
print_backpack(i - 1, j);
}
else {
std::cout << i << " ";
print_backpack(i - 1, j - W[i]);
}
}
}
};
 
int main() {
setlocale(LC_ALL, "Russian");
 
Bacpack a, b;
std::cout << "\n\n";
int q = a.max_vyb();
std::cout << q << "\n";
a.print_backpack(6-1,10-1);
std::cout << "\n\n";
system("pause");
return 0;
}

Реализация процедурным методом

Рюкзак процедурный подход
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <fstream>
 
int len_mass; //длина массива
int **T; //двумерный массив под вычисления
int g = 1; //счетчик
int *W, *C; //массивы для веса и стоимости
 
int maxx(int a, int b) { //функция опредения максимума
if (a > b) {
return a;
}
else {
return b;
}
}
 
int** max_vyb(int n, int P) {
for (int j = 0; j < P; j++) { //заполнили матрицу Т 8-ками
for (int i = 0; i < n; i++) {
T[i][j] = 0;
}
}
 
int buf1, buf2;
int i, j;
for (j = 1; j < P; j++) {
for (i = 1; i < n; i++) {
if (W[i] <= j) {
buf1 = T[i - 1][j];
buf2 = T[i - 1][j - W[i]] + C[i];
T[i][j] = maxx(buf1, buf2);
}
else {
T[i][j] = T[i - 1][j];
}
}
}
std::cout << T[i-1][j-1] << std::endl; //вывод максимальной выборки
return T;
}
 
 
void print_backpack(int i, int j) { //печать выборки
if (T[i][j] == 0) {
std::cout << "\nКол-во: " << g;
std::cout << "\n\n";
system("pause");
exit(1);
}
else {
if (T[i - 1][j] == T[i][j]) {
g++; //счетчик для количества предметов
print_backpack(i - 1, j);
}
else {
std::cout << i << " "; //номера предметов вывод
print_backpack(i - 1, j - W[i]);
}
}
}
 
 
int main() {
setlocale(LC_ALL, "Russian");
 
std::ifstream w("WC.txt");
int temp; //заполнили кол-во предметов
w >> temp;
int n = temp;
 
int q, e;     //запомнили веса и стоимости
int i = 0;
 
W = new int[n]; //вес
C = new int[n]; //стоимость
while (!w.eof()) {
w >> q >> e;
W[i] = q;
C[i] = e;
if (i > 0) {
std::cout << "w" << i << " - " << W[i] << "    c" << i << " - " << C[i] << std::endl; //вывод таблицы значений
}
i++;
}
 
 
int P = W[0]; //заполнили максимальную вес
len_mass = n;
std::cout << "\n\nМакс вес: " << P << "\tМакс кол-во: " << temp << "\n\n";
 
T = new int* [P];
for (int i = 0; i < n; i++) {
T[i] = new int[P];
}
 
int **Z; //это пустая переменная для принятия вычисления массива Т
Z = new int*[P];
for (int i = 0; i < n; i++) {
Z[i] = new int[P];
}
 
Z = max_vyb(n, P);
 
print_backpack(6 - 1, 10 - 1);
 
system("pause");
w.close();
return 0;
}

Post Author: Nikulux

Похожие записи

Добавить комментарий