// ---------- MWSCP.h--------------------------
template <class W>
class WeightedSet {
public:
WeightedSet(W, int);
W weight;
W rweight;
int els;
int *elements;
bool operator <(const WeightedSet<W>&);
bool operator ==(const WeightedSet<W>&);
bool operator >(const WeightedSet<W>&);
};
template <class W>
struct solution {
W cost;
int size;
list<WeightedSet<W> > collections;
};
template <class W>
class MWSCP {
public:
MWSCP(int pels, int pcolls);
int els; // the total number of elements
int colls; //the total number of collections
int* covered; //covered[element]=0 if element is covered by a
current choice of collections
WeightedSet<W> *collections; // collections
solution<W> solveGreedy();
solution<W> solveLayered();
bool check();
};
//---------------------------------MWSCP.cpp------------------------------------
#include <list>
using namespace std;
template <class W>
WeightedSet<W>::WeightedSet(W w, int n) {
// w is the weight, n is the number of elements
weight = w;
els = n;
elements = new int[n];
}
template <class W>
bool WeightedSet<W>::operator <(const WeightedSet<W>& sOperand)
{
return this.rweight < sOperand.rWeight;
}
template <class W>
bool WeightedSet<W>::operator >(const WeightedSet<W>& sOperand)
{
return this.rweight > sOperand.rWeight;
}
template <class W>
bool WeightedSet<W>::operator ==(const WeightedSet<W>& sOperand)
{
return this.rweight == sOperand.rWeight;
}
template <class W>
MWSCP<W>::MWSCP(int pels, int pcolls) {
// pels is the total number of elements, pcolls is the number of
collections
els = pels;
covered = new int[els];
for (int i=0; i < els; i++) covered[i] = 0;
colls = pcolls;
collections = (WeightedSet<W> *)malloc(colls *
sizeof(WeightedSet<W>));
}
template <class W>
solution<W> MWSCP<W>::solveGreedy(){
// solves this instance of the MWSCP
// heap-ified version is defined in MWSCPHeap
W totalcost = 0; int executions = 0;
solution<W> solution;
while (!check() && executions++ < els) {
// choose the lowers price
W mincost = 0;
int collection = 0;
for (int i = 0; i< colls; i++ ){
// check all collections to find a collection with the
minimal cost per uncovered element
W cost;
int notcovered = 0;
WeightedSet<W> c = collections[i];
for (int j = 0; j < c.els; j++) if
(covered[c.elements[j]] == 0 ) notcovered++;
if (notcovered > 0) cost =
c.weight/(static_cast<W>(notcovered));
else continue; // all elements of a given collection are
covered already
if (mincost == 0 /*the first execution*/ || mincost > cost
) {mincost = cost; collection = i; continue;}
}
//int x;
WeightedSet<W> c = collections[collection];
//cout << collection; cout.flush();
totalcost += c.weight;
for (int j = 0; j < c.els; j++) covered[c.elements[j]] = 1;
solution.collections.push_back(c);
for (int k =0; k < els; k++) cout << covered[k]; cout <<
endl;cout.flush();
//cin >> x;
}
solution.size = executions+1;
solution.cost = totalcost;
return solution;
}
template <class W>
solution<W> MWSCP<W>::solveLayered(){
// Heap-fied version is defiend in MWSCPHeap
W residue[colls]; // coefficient of the large-degree function
W coeff; // coefficient of the largest-degree function
solution<W> solution;
for (int i=0; i < colls; i++) residue[i] = collections[i].weight;
list<WeightedSet<W> > SetCover; // a list of collections which will
be chosen at this layer
W totalcost = 0; int executions = 0;
while (!check() && executions++ < els) {
// choose the lowers price
W mincost = 0;
int collection = 0;
for (int i = 0; i< colls; i++ ){
// check all collections to find a collection with the
minimal cost per uncovered element
W cost;
int notcovered = 0;
WeightedSet<W> c = collections[i];
for (int j = 0; j < c.els; j++) if
(covered[c.elements[j]] == 0 ) notcovered++;
if (notcovered > 0) cost =
(residue[i])/(static_cast<W>(notcovered));
else continue; // all elements of a given collection are
covered already
if (mincost == cost) SetCover.push_back(c);
if (mincost == 0 /*the first execution*/ || mincost > cost
)
{mincost = cost; collection = i; coeff = cost/notcovered;
SetCover.clear(); SetCover.push_back(c);
continue;}
}
//int x;
WeightedSet<W> c = collections[collection];
//cout << collection; cout.flush();
// before update we have to compute new residue...it can be
postponed to the next step
for (int i = 0; i < colls; i++){
WeightedSet<W> c = collections[i];
int notcovered = 0;
for (int j = 0; j < c.els; j++) if (covered[c.elements[j]] == 0 )
notcovered++;
residue[i] -= notcovered * coeff;
solution.collections.push_back(c);
}
// HERE
//list<WeightedSet<float> >::iterator iter;
list<WeightedSet<W> >::iterator iter;
for (iter = SetCover.begin(); iter != SetCover.end(); iter++){
totalcost += iter->weight;
solution.size +=1;
for (int j = 0; j < iter->els; j++) covered[iter->elements[j]]
= 1;}
//for (int k =0; k < els; k++) cout << covered[k]; cout <<
endl;cout.flush();
//cin >> x;
for (int k =0; k < els; k++) cout << covered[k]; cout <<
endl;cout.flush();
}
solution.cost = totalcost;
return solution;
}
template <class W>
bool MWSCP<W>::check() {
// check if all elements are covered
for (int i=0; i<els; i++) if (covered[i] == 0) return 0;
return 1;
}
