Frage zu Ranges?

Michael E.

Danke, ich hatte da einen Gedankenfehler.

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

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

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';
}

icarus2

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

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!

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

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

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.

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