Problema cu lingouri de aur

Alocare dinamica (de mana sau cu std::vector) si iti incap elemente cat tine memoria. Dar nici nu trebuie sa le tii pe toate in array, algoritmul gasit le proceseaza pe rand.

ce algoritmi ati folosit?
nu sunt convins ca un algoritm liniar (gen greedy) gaseste intotdeauna solutia optima.

_Smiley_, on 08 iunie 2018 - 17:52, said:

#include <iostream>
#include <fstream>
using namespace std;
main()
{
ifstream lin("input-10.txt");
char s1[5],s2[5],s3[5];
int n;
struct{
	 int x,y,z;
} lingou[100];
lin>>n;
for (int i=0;i<n;i++)
{
	 lin>>s1>>lingou[i].x>>lingou[i].y>>lingou[i].z>>s2>>s3;
}
int aux;
for (int j=0;j<n;j++)
		 if (lingou[j].x>lingou[j].y){
			 aux=lingou[j].x;
			 lingou[j].x=lingou[j].y;
			 lingou[j].y=aux;
		 }
for (int j=0;j<n;j++)
		 if (lingou[j].y>lingou[j].z){
			 aux=lingou[j].y;
			 lingou[j].y=lingou[j].z;
			 lingou[j].z=aux;
		 }
for (int j=0;j<n;j++)
		 if (lingou[j].x>lingou[j].y){
			 aux=lingou[j].x;
			 lingou[j].x=lingou[j].y;
			 lingou[j].y=aux;
		 } /// le aranjez crescator, ca sa scap dea cea mai mare din ele.
int max1=0,max2=0;
for (int i=0;i<n;i++)
	 if (lingou[i].x>max1) max1=lingou[i].x;
for (int i=0;i<n;i++)
	 if (lingou[i].y>max2) max2=lingou[i].y;
cout<<max1*max2<<endl;
return 0;
}

E in c++. L-am explicat in pagina anterioara. Nu functioneaza pentru 100% din cazuri, dar majoritatea sunt corecte. Nu cred ca metoda greedy sa functioneze in acest caz. Oricum metodele alea sunt antice si necesita o gramada de linii de cod. Acum se poate de realizat acelasi lucru in mult mai putine linii, si cu o complexitate mai mica de asemena.

Edited by AlexMatei2000, 08 June 2018 - 18:05.

Algoritmul meu arata cam asa. Nu garantez ca e corect in toate cazurile (daca cineva are cazuri aparte, ar prinde bine niste intrari de test).

Plecand de la eliminarea laturii celei mai mari a fiecarui lingou:

 algoritm.png   177K   13 downloads

Edited by dani.user, 08 June 2018 - 18:12.

AlexMatei2000, on 08 iunie 2018 - 17:59, said:

probabil ca nu-ti dai seama, dar ai folosit fix metoda greedy
si asa cum ti-ai dat singur seama, nu e o solutie corecta. pornesti de la presupunerea ca rezultatul va fi un singur orificiu, si evident ca nu e cazul.

dani.user, on 08 iunie 2018 - 18:03, said:

nu cred ca e corect. la modul minimal, procesarea aleatorie e a lingourilor nu garanteaza un rezultat bun. uite un contraexemplu: 3 lingouri , unul de 3x4, unul de 1x7 si altul de 100x100. algoritmul tau va procesa intai primele 2 lingouri si va decide ca e nevoie de 2 orificii, apoi va procesa ultimul lingou si in cel mai bun caz va decide sa mareasca unul dintre orificii, rezultand in final doua orificii. rezultatul corect este, evident, un singur orificiu (de 100x100) prin care pot fi scoase toate lingourile.

ma intreb daca se poate demonstra matematic ca renuntarea la latura cea mai mare nu afecteaza obtinerea unui optim...

Bun exemplu. Cred ca l-ar rezolva algoritmul meu daca sortez initial lingourile in ordine descrescatoare (a ariei probabil).

Renuntarea la latura cea mai mare nu o vad ca o dificultate matematica. Practic cautam cea mai mica proiectie in plan a lingoului, latura cea mai mare fiind perpendiculara pe acea proiectie, deci irelevanta.