-
Notifications
You must be signed in to change notification settings - Fork 0
/
FPTASKnapsackSolver.cpp
41 lines (35 loc) · 993 Bytes
/
FPTASKnapsackSolver.cpp
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
#include "FPTASKnapsackSolver.h"
#include "DynamicKnapsackSolver.h"
using namespace std;
bool FPTASKnapsackSolver::Solve()
{
//PrintParams();
int maxValue = GetSumValue();
double K = m_eps * maxValue / m_N;
//cout << "eps=" << m_eps << " K=" << K << endl;
int b = (int)floor(log2(K));
//cout << "shifting " << b << "bits" << endl;
int * new_values = new int[m_N];
int * new_weights = new int[m_N];
for (int i = 0; i < m_N; i++){
new_values[i] = m_items[i].value >> b;
new_weights[i] = m_items[i].weight;
}
DynamicKnapsackSolver* solver = new DynamicKnapsackSolver;
solver->LoadNewParams(m_M, m_N, new_weights, new_values, m_id);
solver->SetSilent(true);
//solver->PrintParams();
solver->Solve();
m_result_vector = solver->GetResultVector();
m_current_best_price = 0;
for (int i = 0; i < m_N; i++){
if (m_result_vector->at(i) == 1){
m_current_best_price += m_items[i].value;
}
}
return true;
}
void FPTASKnapsackSolver::SetError(double in)
{
m_eps = in;
}