EGALabs/GreedyBackpackSearchMethod.cpp at master · MalchuL/EGALabs · GitHub

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
#include "stdafx.h"
#include "GreedyBackpackSearchMethod.h"

bool BackpackSearchMethod::GreedyBackpackSearchMethod::compare(object first, object second) {
	//Âçÿòü èç ïåðâîé ïàðû è èç âòîðîé òîëüêî èõ ñòîèìîñòè è ñðàâíèòü
	if (get<COST>(first) == get<COST>(second)) return  get<WEIGHT>(first) > get<WEIGHT>(second);
	return get<COST>(first) < get<COST>(second);
}

BackpackSearchMethod::GreedyBackpackSearchMethod::GreedyBackpackSearchMethod(vector<weightvalue> weights, vector<costvalue> costs, weightvalue maxWeight) :AbstractBackpackSearchMethod(weights, costs, maxWeight) {}

ByteVector BackpackSearchMethod::GreedyBackpackSearchMethod::find() {
	clog << "in list" << endl;
	printList(*objects);
	costvalue currentCost = 0;
	weightvalue currentWeight = 0;
	ByteVector returnedvector(objects->size());
	sort(objects->begin(), objects->end(), compare);
	reverse(objects->begin(), objects->end());
	clog << "\n\n\sorted list" << endl;
	printList(*objects);

	for (size_t i = 0; i < objects->size(); i++)
	{
		if (currentWeight + get<WEIGHT>(objects->at(i)) <= maxWeight) {
			currentCost += get<COST>(objects->at(i));
			currentWeight += get<WEIGHT>(objects->at(i));
			returnedvector.setByte(get<INDEX>(objects->at(i)), 1);
			clog << "set byte at pos:" << get<INDEX>(objects->at(i)) << " cost:" << currentCost << " weight:" << currentWeight << endl;
		}
		else
		{
			//Èíà÷å ìá óæå ñ ìèíèìàëüíûìè âåññàìè, íî ñ ñàìîé ìàëåíüêîé ñòîèìîñòüþ
		}
	}
	clog << "Cost:" << currentCost << " Weight:" << currentWeight << endl;

	return ByteVectorMath::Reverse(returnedvector);

}