Greedy परिचय

एक greedy algorithm हर बार jar में हाथ डालने पर सबसे बड़ी cookie चुनने जैसा है। यह हमेशा वह चुनता है जो अभी सबसे अच्छा दिखे और उम्मीद करता है कि यह एक अच्छे result तक add हो।

In this page:

What is Greedy?
Greedy Choice
Local Best
When Greedy Works
Practice

Syntax

markup

result = []
for choice in sorted_candidates:    # order by greedy rule
    if is_feasible(choice, result):
        result.append(choice)

What is Greedy?

एक greedy algorithm step by step एक solution बनाता है, हमेशा जो भी choice अभी सबसे अच्छी दिखे वह करते हुए, और बाद में कभी उस choice को revisit या reconsider नहीं करता — यह bet करते हुए कि locally-best decisions की एक sequence एक globally-best result तक add हो।

उदाहरण: What is Greedy?

#include <iostream>
using namespace std;
int main() {
	cout << "Greedy: pick whichever choice looks best right now, never revisit that choice later";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Greedy: pick whichever choice looks best right now, never revisit that choice later");
	}
}

print("Greedy: pick whichever choice looks best right now, never revisit that choice later")

#include <stdio.h>
int main() {
	printf("Greedy: pick whichever choice looks best right now, never revisit that choice later");
	return 0;
}

Greedy Choice

एक greedy choice सिर्फ तब trustworthy है अगर यह provably safe हो — मतलब कुछ optimal solution इस choice से agree करने की guarantee के साथ मौजूद हो — क्योंकि एक greedy algorithm के पास एक बार commit होने के बाद decision undo करने का कोई mechanism नहीं।

उदाहरण: Greedy Choice

#include <iostream>
using namespace std;
int main() {
	cout << "A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it");
	}
}

print("A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it")

#include <stdio.h>
int main() {
	printf("A greedy choice is trustworthy only if some optimal solution is provably guaranteed to agree with it");
	return 0;
}

Local Best

Problem के आधार पर, 'अभी सबसे अच्छा' का मतलब सबसे early deadline, सबसे छोटा weight, सबसे बड़ी value, या सबसे ज़्यादा profit-to-cost ratio हो सकता है — specific rule हमेशा यह prove करने से आती है कि उस particular problem के लिए एक choice को क्या safe बनाता है।

उदाहरण: Local Best

#include <iostream>
using namespace std;
int main() {
	string rules[] = {"earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"};
	for (string r : rules) cout << r << "; ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] rules = {"earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"};
		for (String r : rules) System.out.print(r + "; ");
	}
}

rules = ["earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"]
print("; ".join(rules))

#include <stdio.h>
int main() {
	char* rules[] = {"earliest deadline", "smallest weight", "largest value", "highest profit-to-cost ratio"};
	for (int i = 0; i < 4; i++) printf("%s; ", rules[i]);
	return 0;
}

When Greedy Works

Greedy strategies सिर्फ उन problems के लिए एक correct answer produce करती हैं जिनके पास असल में सही mathematical structure है (अक्सर greedy-choice property और optimal substructure कहलाता है) — इस structure की कमी वाली किसी problem पर एक greedy rule apply करना चुपचाप एक गलत answer produce कर सकता है जो plausible दिखता है।

उदाहरण: When Greedy Works

#include <iostream>
using namespace std;
int main() {
	cout << "Requires greedy-choice property AND optimal substructure -- not every problem has this structure";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Requires greedy-choice property AND optimal substructure -- not every problem has this structure");
	}
}

print("Requires greedy-choice property AND optimal substructure -- not every problem has this structure")

#include <stdio.h>
int main() {
	printf("Requires greedy-choice property AND optimal substructure -- not every problem has this structure");
	return 0;
}

Practice

एक नई optimization problem का सामना करते समय एक अच्छी आदत है हाथ से छोटे examples try करना, notice करना कि कौन सी local choice लगातार सबसे अच्छा outcome produce करती है, और फिर सामान्य में इस पर भरोसा करने से पहले यह prove करने की कोशिश करना कि वह choice हमेशा safe है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Try small examples by hand, notice which local choice always wins, then try to prove it";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Try small examples by hand, notice which local choice always wins, then try to prove it");
	}
}

print("Try small examples by hand, notice which local choice always wins, then try to prove it")

#include <stdio.h>
int main() {
	printf("Try small examples by hand, notice which local choice always wins, then try to prove it");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson DP on Trees Next Lesson → Activity Selection Problem