ਇੱਕ ਲਾਲਚੀ ਐਲਗੋਰਿਦਮਹਰ ਪੜਾਅ ਤੇ ਸਥਾਨਕ ਤੌਰ ਤੇ ਸਰਵੋਤ੍ਤਮ ਚੋਣਕਰਦਾ ਹੈ, ਏਸ ਉਮੀਦ ਨਾਲ ਕਿ ਇਹ ਗਲੋਬਲ ਸਰਵੋਤ੍ਤਮ ਵੱਲ ਲੈ ਜਾਵੇ। ਇਹ ਸਰਲ ਅਤੇ ਤੇਜ਼ ਹੈ, ਪਰ ਸਿਰਫ ਤਦ ਸਠੀਕ ਹੈ ਜਦੋਂ ਸਮੱਸਿਆ ਲਾਲਚੀ-ਚੋਣ ਵਿਸ਼ੇਸ਼ਤਾਅਤੇ ਸਰਵੋਤ੍ਤਮ ਉਪ-ਬਣਤਰ ਰੱਖਦੀ ਹੈ।
ਅਤੀਤ ਦੀ ਚੋਣਾਂ ਤੇ ਦੁਬਾਰਾ ਵਿਚਾਰ ਨਾ ਕਰੋ — ਸਭ ਤੋਂ ਬਿਹਤਰ ਤਤਕਾਲ ਵਿਕਲਪ ਲਈ ਪ੍ਰਤਿਬੱਧ ਹੋ ਅਤੇ ਅੱਗੇ ਵਧੋ।
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
ਇਹ ਅਮਰੀਕੀ ਸਿੱਕਿਆਂ ਲਈ ਸਰਵੋਤ੍ਤਮ ਹੈ, ਪਰ {1, 3, 4} ਜਿਵੇ ਸੈੱਟਾਂ ਲਈ ਅਸਫਲ ਹੁੰਦਾ ਹੈ ਜਿੱਥੇ ਲਾਲਚੀ 6 ਲਈ 3+3 ਦੀ ਜਗ੍ਹਾ 4+1+1 ਦਿੰਦਾ ਹੈ।
ਕੰਮ ਕਰਨ ਵਾਲੀਆਂ ਉਦਾਹਰਨਾਂ: Dijkstra, Kruskal/Prim (MST), Huffman ਕੋਡਿੰਗ, ਅੰਤਰਾਲ ਸ਼ਿਡਿউਲਿੰਗ।
ਆਮ ਤੌਰ ਤੇ ਤੇਜ਼ — ਅਕਸਰ ਛਾਂਟਣ ਤੋਂ ਬਾਅਦ O(n log n)।
ਲਾਲਚੀ ਹਮੇਸ਼ਾ ਸਠੀਕ ਨਹੀਂ ਹੈ। ਲਾਲਚੀ-ਚੋਣ ਵਿਸ਼ੇਸ਼ਤਾ ਸਾਬਤ ਕਰੋ ਜਾਂ ਇਸ ਤੇ ਭਰੋਸਾ ਕਰਨ ਤੋਂ ਪਹਿਲਾਂ ਬਿਰੂਟ-ਫੋਰਸ/DP ਬੇਸਲਾਈਨ ਵਿਰੁੱਧ ਟੈਸਟ ਕਰੋ।
ਜਦੋਂ ਲਾਲਚੀ ਲਾਗੂ ਹੁੰਦਾ ਹੈ, ਇਹ DP ਜਾਂ ਬਿਰੂਟ ਫੋਰਸ ਨਾਲੋਂ ਬਹੁਤ ਸਰਲ ਅਤੇ ਤੇਜ਼ ਹੈ।
ਕਦੋਂ ਇਹ ਵੈਧ ਹੈ — ਅਤੇ ਕਦੋਂ ਇਹ ਚੁੱਪ ਨਾਲ ਗਲਤ ਜਵਾਬ ਦਿੰਦਾ ਹੈ ਜਾਣਨਾ — ਇਹ ਐਲਗੋਰਿਦਮਿਕ ਪਰਿਪੱਕਤਾ ਦਾ ਨਿਸ਼ਾਨ ਹੈ।
ਬਹੁਤ ਸਾਰੀਆਂ ਮੁੱਖ ਗ੍ਰਾਫ ਐਲਗੋਰਿਦਮ ਦਿਲ ਵਿਚ ਲਾਲਚੀ ਹਨ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ