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
|
#include <iostream>
// Това е значително по-просто решение, аз не се сетих, взех от Катрин Попова
int knapsack2(int i, int *values, int *weights, int size, int maxWeight) {
if (i == size)
return 0;
int currentNotTaken = knapsack2(i+1, values, weights, size, maxWeight);
if (weights[i] <= maxWeight) {
int currentTaken = values[i] + knapsack2(i+1, values, weights, size, maxWeight - weights[i]);
return currentTaken > currentNotTaken ? currentTaken : currentNotTaken;
}
return currentNotTaken;
}
// Това е решението, показано на практикума
void knapsack1(int i, int& maxValues, bool *taken, int *values, int *weights, int size, int maxWeight) {
if (i == size) {
int currentValues = 0, currentWeight = 0;
for (int i = 0; i < size; i++) {
if (taken[i]) {
currentValues += values[i];
currentWeight += weights[i];
}
}
if (currentWeight > maxWeight) return;
if (currentValues > maxValues) {
maxValues = currentValues;
}
return;
}
taken[i] = false;
knapsack1(i+1, maxValues, taken, values, weights, size, maxWeight);
taken[i] = true;
knapsack1(i+1, maxValues, taken, values, weights, size, maxWeight);
}
int main() {
int N;
std::cin >> N;
int *values = new int[N];
int *weights = new int[N];
for (int i = 0; i < N; i++) {
std::cin >> values[i] >> weights[i];
}
int maxWeight;
std::cin >> maxWeight;
int maxValues = 0;
bool *taken = new bool[N];
knapsack1(0, maxValues, taken, values, weights, N, maxWeight);
std::cout << maxValues << std::endl;
delete[] taken;
std::cout << knapsack2(0, values, weights, N, maxWeight) << std::endl;
delete[] values;
delete[] weights;
}
|
