1
1

Greedy এলগরিদম এ তো সবসময়ই অপ্টিমাল রেসাল্ট পাওয়া যায় না যেখানে ডায়নামিক প্রোগ্রামিং‬ এলগরিদম এ অপ্টিমাল রেসাল্ট পাওয়া যায় । তাহলে কেন আমরা Greedy এলগরিদম ব্যাবহার করি এবং কেন করি ?

asked 28 Jul '16, 18:39

Md%20Alamin's gravatar image

Md Alamin
214

edited 28 Jul '16, 18:44


Greedy Algorithm যেখানে apply করা যায়, সেখানে তো ডায়নামিক প্রোগ্রামিং‬ এলগরিদম করা যাবেই। আপনি যদি ডায়নামিক প্রোগ্রামিং‬ এলগরিদম ব্যবহার করতে চান তবে আপনাকে কেউ বাধা দিবে না।

এখন প্রশ্ন হচ্ছে কেন আমরা ডায়নামিক প্রোগ্রামিং‬ এলগরিদম ব্যবহার করি না Greedy এর ক্ষেত্রে?

উত্তর হচ্ছে যেখানে Greedy Algorithm ব্যবহার করেলেই হয়ে যাচ্ছে সেখানে কেন ডায়নামিক প্রোগ্রামিং‬ এলগরিদম ব্যবহার করবো? ডায়নামিক প্রোগ্রামিং‬ এলগরিদম এর ক্ষেত্রে বেশিরভাগ সময় Memory and Time Complexity তুলনামুলক বেশি হয়। কিছু সময় কোড কমপ্লেক্স হয়। তাই সবকিছু মাথায় রেখেই কোড করতে হবে।

একটি উদাহরন দেই। আপানাকে N টাকা দেওয়া হল আর বলা হল X টা প্রোডাক্ট থেকে সর্বোচ্চ কয়টা প্রোডাক্ট নিতে পারবেন যাদের দাম C1,C2...Cx করে? আপনি কি করবেন?

প্রোডাক্ট গুলো মূল্য অনুযায়ী সর্ট করে কাউন্ট করবেন যতক্ষণ পর্যন্ত Total Cost, N এর সমান বা বেশি না হয়। এটা কিন্তু Greedy Algorithm।

কিন্তু যদি বলা হয় আপানাকে N টাকা দেওয়া হল আর W ওজন বহন কারী একটি ব্যাগ দেওয়া হল এবং বলা হল এই টাকার ও ওজনের মধ্যে X টা প্রোডাক্ট থেকে সর্বোচ্চ কয়টা প্রোডাক্ট নিতে পারবেন যাদের দাম C1,C2...Cx ও ওজন W1,W2...Wx করে?

তখন কিন্তু ডায়নামিক প্রোগ্রামিং‬ টেকনিক ব্যবহার করবেন।

permanent link

answered 29 Jul '16, 14:55

Kaiser%20Ahmed's gravatar image

Kaiser Ahmed
3.2k1622

edited 29 Jul '16, 17:12

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×63
×37
×10
×3
×1

question asked: 28 Jul '16, 18:39

question was seen: 1,294 times

last updated: 29 Jul '16, 17:12