Doar ca mie imi da ca output 9 8 7 6 (imi ignora cel de al doilea 8). Nu stiu ce sa i mai fac, nu stiu daca am folosit metoda greedy (nu prea stiu exact cum se face algoritm greedy)
Eu am incercat sa fac in C codul.
#include <stdio.h>
#include <stdlib.h>
int maxim(int a, int b)
{
if( a > b)
return a;
else
return b;
}
int main() {
int i, j, n, a[999], m, aux, sum = 0, v[999], k = 0, x[999], c, t=0, q, r;
int max = 0;
printf("No. of objects (type 8): ");
scanf("%d", &n);
printf("\nNo. of objects for first place (type 4): ");
scanf("%d", &m);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
r = m;
for (i = 0; i < n; i++)
{
if(a[i] > max)
{
max = a[i];
}
}
x[0] = max;
for(i = 1; i < n; i++){
max = 0;
for(j = 0; j < n; j++)
{
if(a[j] > max && a[j] < x[i - 1])
{
max = a[j];
}
}
x[i] = max;
}
for(t = 0; t < m; t++)
{
printf("%d", x[t]);
}
return 0;
}
Multe abordari greedy se bazeaza pe o preprocesare a datelor de intrare. In cazul tau ar fi vorba de o sortare si dupa pe array-ul sortat iti faci treaba
Salutare,
In primul rand cred ca proful tau nu prea intelege la ce se refera greedy.
Sper sa te ajute explicatia de aici: Greedy algorithm - Wikipedia
Daca nu, poti sa ne intrebi legat de ce nu ai inteles.
Inainte sa te ajutam, spune-ne in cuvinte cum te-ai gandit sa rezolvi problema.
Exista o solutie mult mai eficienta si aproape la fel de scurta care nu implica sortare.
Desigur ca exista o solutie mult mai eficienta, dar in spiritul Greedy cam asta ar fi.
Trebuie sa facem aici diferenta intre un exercitiu de invatare si un exercitiu “pe bune”. De exemplu mai incolo poate sa-i zica profesorul: “Ai problema asta” rezolva problema Greedy si apoi dynamic. Important e sa poata sa isi dea si seama de diferentele intre cele doua, poate asta e si scopul exercitiului curent.
Ideea ar fi sa nu furi o oportunitate de invatare a cuiva. Cum ar fi sa inveti sa conduci la scoala de soferi si apoi sa-ti vina tatal si sa-ti zica ca nu inveti cum trebuie si sa se bage peste instructor?
Daca instructorul te invata prost si faci accident daca nu te invata cum trebuie, e normal sa se bage altcineva.
Ideea e ca si eu in clasa a 9-a m-am tot chinuit sa inteleg diferentele dintre metoda greedy si metoda programarii dinamice. Problema era ca invatam din manualul de clasa a 11-a unde erau niste explicatii total proaste. De exemplu problema rucsacului care e clasica de programare dinamica era la greedy.
Majoritatea profilor nu inteleg greedy/programare dinamica si le predau cuvant cu cuvant din niste manuale scrise de niste profi care au ajuns sa le scrie datorita influentei pe care o aveau si nu datorita skill-urilor in programare.
Adevarul e ca problema din enunt are 0 legatura cu greedy sau cu programare dinamica si face doar sa induca in eroare pe cineva care invata greedy.
Eu sunt de acord aici. Realitatea e că în licee (și nu mă refer la liceele de top din orașele mari din țară, mă refer la restul prin orașe mai mici) povestea cu informatica e… sub orice critică. Nu mai vreau să mă apuc să povestesc ce experiențe am avut eu cu profesorul meu de info la liceu care, pe lângă faptul că se vedea de la o poștă că nu e bine pregătit absolut deloc, mai făcea și mișto de noi că habar n-avem să rezolvăm problemele lui pe care le găsea la olimpiade și nici măcar nu le înțelegea (și avea și o lipsă totală de interes). Cireașa de pe tort e că mai aveam și directorul care susținea că suntem al nu știu câtelea liceu pe țară…
Am rezolvat codul pana la urma, am uitat sa las aici un update. Va multumesc pentru interesul acordat!
using System;
using System.Linq;
//using System.Collections.Generic;
using System.Collections;
public class greedyMax
{
static int greedyRec(int[] numbers, int count)
{
int maxValue = numbers.Max(); //Gaseste max. din sir
int maxIndex = numbers.ToList().IndexOf(maxValue); //Returneaza index numar max. din sir
Console.Write(maxValue.ToString() + " "); //Afiseaza max din numere
if (count > 1) //Verifica daca s-au gasit cele 4 valori maxime
//Se apeleaza functia greedyRec de numbers fara maxVal
return maxValue + greedyRec(numbers.Where((val, idx) => idx != maxIndex).ToArray(), count - 1);
return maxValue;
}
public static void Main(string[] args)
{
int val= 0;
//Try verifica daca este introdus un numar, nu accepta caractere
try
{
Console.Write("Nr. obiecte: "); //
val = Convert.ToInt32(Console.ReadLine()); //Citeste de la tastatura un numar
}
//Daca s-a introdus un caracter (!= numar) se opreste programul
catch
{
Console.WriteLine("Eroare, caracterul introdus este invalid!");
return;
}
int[] numbers = new int[val]; //Declara un sir de int-uri
for (int i = 0; i < val; i++)
{
try
{
Console.Write("Obiect {0}: ", i + 1);
numbers[i] = Convert.ToInt32(Console.ReadLine()); //Citeste valorile sirului
}
catch
{
Console.WriteLine("Eroare, caracterul introdus este invalid!");
return;
}
}
Console.Write("Numerele maxime= ");
Console.WriteLine("\nmaxSum = " + greedyRec(numbers, 4).ToString()); //Afiseaza suma celor 4 max-uri gasite
}
}
Eu zic ca este un exemplu bun de problema greedy, poate ca este prea “toy problem” sa zic asa.
Conform wikipedia:
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
Folosind definitia, solutia greedy in cazul curent este sa avem o structura de date care tine cele 4 elemente care sunt cele mai mari 4 numere.
Structura de date se initializeaza greedy (solutia optima la pasul 0) cu primele 4 elemente din sir.
Cand se parcurge sirul, la fiecare pas, alegerea greedy este sa modificam acea structura de date in cazul in care elementul curent este mai mare decat oricare din cele 4 elemente existente.
Modificarea consta in eliminarea celui mai mic din cele 4 si inlocuirea cu elementul curent.
In felul acesta la final vom avea cele mai mari 4 elemente (chiar daca toate au aceeasi valoare).
Problema clar este simpla si sunt convins ca toata lumea stie solutia optima.
Am scris deoarece discutia incepuse se fie “profii nu stiu greedy etc”, cand e absolut clar ca problema este un exemplu bun de greedy. Clasificarile acestea de algoritmi nu sunt alb/negre si intr-adevar cand problema este simpla, punerea unui label poate parea putin ridicola. De asemenea o problema poate cadea sub multiple clasificari in aceelasi timp.
Riscul este ca OP ar putea pleca cu ideea ca proful nu stie ce zice, problema e proasta si de aceea el ia nota mica cu solutia “mai buna”, nu pentru ca nici nu a citit definita.
