3. Frage zu Ranges?

Frage zu Ranges?

  • ?

    also mal angenommen ich hab paar ranges und jede range hat ein gewicht:

    1-3 | 0.5
    2-5 | 0.2
    4-7 | 0.3
    2-7 | 0.4
    6-9 | 0.1

    wie find ich dann eine nicht überlappende kombination mit möglichst hohem gewicht 😕

    0
  • ?

    Die Grundidee für eine O(log n)-Lösung ist recht einfach:
    Du sortierst alle Ranges nach den Endpunkten.
    Dann gehst du die Ranges der Reihe nach durch.
    Für Range a_i - b_i mit Gewicht w_i berechnest du:
    Das beste Resultat bis b_i ist max{(bestes Resultat bis a_i) + w_i, bestes Resultat bis w_{i-1}}.

    0
  • ?

    Äh, natürlich O(n log n)

    0
  • M

    Die Idee einer Sweepline ist gut, aber ich sehe erst mal nicht, wie man das in O(n log n) implementieren kann. Kannst du da bitte ein wenig näher drauf eingehen?

    0
  • ?

    Ich meinte das etwa so:

    #include <iostream>
#include <algorithm>
#include <map>

int main()
{
  struct range { int from, to; double w; } rs[] = {
    { 1, 3, 0.5 },
    { 2, 5, 0.2 },
    { 4, 7, 0.3 },
    { 2, 7, 0.4 },
    { 6, 9, 0.1 },
  };
  std::sort(std::begin(rs), std::end(rs),
            [](range const& l, range const& r){return l.to < r.to; });
  std::map<int, double, std::greater<int> > best_so_far{{-1,0}};
  for (auto const& r : rs)
    best_so_far.insert({r.to, std::max(best_so_far.lower_bound(r.to)->second,
                                       best_so_far.lower_bound(r.from)->second + r.w)});
  std::cout << best_so_far.begin()->second << std::endl;
}

    Kann zwar noch optimiert werden in dem auf die map verzichtet wird, aber die Grundidee sollte klar sein.

    0
  • M

    Danke, ich hatte da einen Gedankenfehler.

    0
  • ?

    Danke! Ist das C++11 oder C++0x und bekommt man sowas mit einem GCC 4.4.5 compiliert oder stell ich mich mal wieder besonders doof an 😞

    0
  • ?
     

    error: ‘begin’ is not a member of ‘std’
error: ‘end’ is not a member of ‘std’

    ufasoft schrieb:

    Old GCC version

    std::begin() exists in C++11 standard and in GCC 4.7 C++ header files.

    - http://ufasoft.com/forum/index.php?PHPSESSID=4ljfaeb8ob8ao8e8294pr37fq4&topic=2295.msg3398#msg3398

    0
  • ?

    Richtig geraten, das war C++11. Spart halt schon manche Zeilen an Code.

    Das kompiliert sogar auf gcc-4.3.2:

    #include <iostream>
#include <algorithm>
#include <vector>

struct range {
  int from, to;
  double w;
};
bool operator<(range const& l, range const& r) { return l.to < r.to; }

struct until_now {
  until_now(int pos, double w) : pos(pos), w(w) {}
  int pos;
  double w;
};
bool operator<(until_now const& l, int pos) { return l.pos > pos; }

int main()
{
  std::vector<range> ranges;
  for (range r; std::cin >> r.from >> r.to >> r.w;)
    ranges.push_back(r);
  std::sort(ranges.begin(), ranges.end());

  std::vector<until_now> dp;
  dp.push_back(until_now(-1, 0)); // vorausgesetzt alle Rangeanfänge sind >0
  for (std::vector<range>::const_iterator it=ranges.begin(); it!=ranges.end(); ++it) {
    double w = std::max(dp.back().w,
                        std::lower_bound(dp.rbegin(), dp.rend(), it->from)->w + it->w);
    if (dp.back().pos == it->to) dp.back().w = std::max(dp.back().w, w);
    else dp.push_back(until_now(it->to, w));
  }
  std::cout << dp.back().w << '\n';
}
    0
  • I

    gefragt schrieb:

    Danke! Ist das C++11 oder C++0x und bekommt man sowas mit einem GCC 4.4.5 compiliert oder stell ich mich mal wieder besonders doof an 😞

    Du musst eventuell ein Compiler Flag setzen, d.h. wenn du z.B. main.cpp kompilieren willst:
    g++ -std=c++11 -o main main.cpp

    0
  • ?

    Mein GCC kennt nur -std=c++0x. Aber es läuft und wenn ich es jetzt dann auch noch verstanden hab, kann ich es portieren und geh ins Betti. Vielen Dank für die Hilfe!

    0
  • ?

    Nun muss ich nochmal fragen...

    #include <iostream>
#include <algorithm>
#include <map>
#include <array>
#include <vector>

typedef struct _range_t{
	int id;
	int from;
	int to;
	double w;
}range;

struct until_now {
  until_now(int id,int pos, double w) : id(id), pos(pos), w(w) {}
  int id;
  int pos;
  double w;
};

bool operator<(until_now const& l, int pos) { return l.pos > pos; }

bool mycmp(range const& l, range const& r){return l.to < r.to; }

int main()
{
  std::array<range,6> rs = {
    {{ 91, 1, 3, 0.5 },
    {  92, 2, 5, 0.2 },
    {  93, 4, 7, 0.3 },
    {  94, 2, 7, 0.4 },
    {  95, 6, 9, 0.1 },
	{  96,10,14, 0.1 }}
  };

  std::sort(rs.begin(),rs.end(),mycmp);

  for ( auto it = rs.begin(); it != rs.end(); ++it ){
	auto r = *it;
	printf("{%d,%d,%d,%f}\n",r.id,r.from,r.to,r.w);
  }

  std::vector<until_now> dp;
  dp.push_back(until_now(0,-1, 0)); // vorausgesetzt alle Rangeanfänge sind >0
  for (auto it=rs.begin(); it!=rs.end(); ++it) {
	auto lb = std::lower_bound(dp.rbegin(), dp.rend(), it->from);
    double w = std::max(
			 dp.back().w
			,lb->w + it->w
	);
	if(dp.back().w > lb->w + it->w){
		std::cout << it->id << "(" << it->w << ")" << " <= " << dp.back().id << "(" << dp.back().w << ")" << '\n';
	}else{
		std::cout << it->id << "(" << it->w << ")"  << " <+ " << lb->id << "(" << lb->w << ")" << '\n';
	}
    if (dp.back().pos == it->to){
		dp.back().w = std::max(dp.back().w, w);
	}else{
		std::cout << "-> " << it->id << "(" << w << ")" << '\n';
		dp.push_back(until_now(it->id,it->to, w));
	}
  }

  std::cout << dp.back().w << '\n';

  for ( auto it = dp.begin(); it != dp.end(); ++it ){
	auto r = *it;
	printf("{%d,%d,%f}\n",r.id,r.pos,r.w);
  }

  //std::cout << best_so_far.begin()->second << std::endl;
}

    Erzeugt folgende Ausgabe:

    {91,1,3,0.500000}
{92,2,5,0.200000}
{93,4,7,0.300000}
{94,2,7,0.400000}
{95,6,9,0.100000}
{96,10,14,0.100000}
91(0.5) <+ 0(0)
-> 91(0.5)
92(0.2) <= 91(0.5)
-> 92(0.5)
93(0.3) <+ 91(0.5)
-> 93(0.8)
94(0.4) <= 93(0.8)
95(0.1) <= 93(0.8)
-> 95(0.8)
96(0.1) <+ 95(0.8)
-> 96(0.9)
0.9
{0,-1,0.000000}
{91,3,0.500000}
{92,5,0.500000}
{93,7,0.800000}
{95,9,0.800000}
{96,14,0.900000}
Press ENTER to continue...

    Was bedeuten würde, die Kette 91 -> 93 -> 96 hat das höchste Gewicht? Stimmt das so? Also ich mein, dass ein 'id <= id' für eine Ersetzung und 'id <+ id' für eine Verkettung steht 😕

    Hoffentlich ist das jetzt nicht total wirr 😞

    0
  • ?

    Problem ist, dass ich wissen muss welche Kettenglieder an der Kombination mit dem höchsten Gewicht beteiligt sind. Reinfrickeln kann ich es schon. Die Frage ist eher ob ich gerade an den richtigen Stellen fummle 😕

    0
  • ?

    In until_now musst du nicht nur die eigene ID, sondern auch die des Vorgängers speichern. Dann kannst du die Zusammensetzung rekonstruieren, wenn du in dp rückwärts läufst. Pass dabei auf, dass du auch im Gleichheitsfall die Werte entsprechend anpasst.

    0
  • ?

    Danke schwiep für die schnelle Anwort! Werd den Quelltext dann posten.

    0
Anmelden zum Antworten