EGALabs/GreedyDancigBackpackSearchMethod.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
41
42
43
44
45
#include "stdafx.h"
#include "GreedyDancigBackpackSearchMethod.h"

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

void BackpackSearchMethod::GreedyDancigBackpackSearchMethod::PrintWeightList(list & printedList) {
	for (object i : printedList) {
		clog << "i:" << get<INDEX>(i) << " w:" << get<WEIGHT>(i) << " c:" << get<COST>(i) << " c/w:" << get<COST>(i) / get<WEIGHT>(i) << endl;
	}
}

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

ByteVector BackpackSearchMethod::GreedyDancigBackpackSearchMethod::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;
	PrintWeightList(*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);

}