উন্নয়ন প্রকল্পগুলি আপনি যা ভাবেন তার চেয়ে প্রায়শই বিভিন্ন অ্যালগরিদম ব্যবহার করে। উদাহরণস্বরূপ, ধরুন আমাদের কিছু ডেটা নির্দিষ্ট প্যারামিটার (কলাম) দ্বারা সাজাতে হবে যাতে আমরা অনেক প্রচেষ্টা ছাড়াই ডেটার মাধ্যমে নেভিগেট করতে পারি। সুতরাং একজন চাকরির ইন্টারভিউয়ারের জন্য আপনাকে একটি নির্দিষ্ট মৌলিক অ্যালগরিদম সম্পর্কে জিজ্ঞাসা করা এবং সম্ভবত কোড ব্যবহার করে এটি বাস্তবায়নের কাজ দেওয়া মোটেই অদ্ভুত হবে না। এবং যেহেতু আপনি এই ওয়েবসাইটে আছেন, আমি এতটা সাহসী হব যে আপনি জাভাতে লিখছেন। এই কারণেই আজ আমি আপনাকে কিছু মৌলিক অ্যালগরিদম এবং জাভাতে কীভাবে প্রয়োগ করতে হয় তার নির্দিষ্ট উদাহরণগুলির সাথে নিজেকে পরিচিত করার পরামর্শ দিচ্ছি। "কিছু" দ্বারা, আমি বলতে চাচ্ছি:
অ্যারে সাজানোর অ্যালগরিদমের ওভারভিউ:
বুদবুদ সাজানো,
নির্বাচন বাছাই,
সন্নিবেশ বাছাই,
শেল সাজানো,
দ্রুত বাছাই,
একত্রিত করা,
লোভী অ্যালগরিদম
পাথফাইন্ডিং অ্যালগরিদম
গভীরতা-প্রথম অনুসন্ধান
প্রস্থ-প্রথম অনুসন্ধান
Dijkstra এর সংক্ষিপ্ত পথ প্রথম অ্যালগরিদম
ঠিক আছে, আর কোনো ঝামেলা ছাড়াই, আসুন ব্যবসায় নেমে আসি।
1. অ্যালগরিদম সাজানোর ওভারভিউ
বুদবুদ সাজানোর
এই সাজানোর অ্যালগরিদম প্রাথমিকভাবে এর সরলতার জন্য পরিচিত, তবে এটি সবচেয়ে ধীরগতিরও একটি। একটি উদাহরণ হিসাবে, আসুন আরোহী ক্রমে সংখ্যার জন্য একটি বুদবুদ বাছাই বিবেচনা করা যাক। আসুন সংখ্যার একটি এলোমেলো ক্রম কল্পনা করি। ক্রমটির শুরু থেকে শুরু করে আমরা এই সংখ্যাগুলিতে নিম্নলিখিত পদক্ষেপগুলি সম্পাদন করব:
দুটি সংখ্যা তুলনা;
যদি বাম দিকের সংখ্যাটি বড় হয় তবে সেগুলি অদলবদল করুন;
একটি অবস্থান ডানদিকে সরান।
পুরো ক্রমটিতে এই পদক্ষেপগুলি সম্পাদন করার পরে, আমরা দেখতে পাব যে বৃহত্তম সংখ্যাটি আমাদের সংখ্যার সিরিজের শেষে রয়েছে। তারপরে আমরা অনুক্রমের উপরে আরেকটি পাস তৈরি করি, উপরের মতো ঠিক একই ধাপগুলি সম্পাদন করি। কিন্তু এইবার আমরা তালিকার শেষ উপাদানটি অন্তর্ভুক্ত করব না, যেহেতু এটি সবচেয়ে বড় সংখ্যা এবং ইতিমধ্যেই সঠিকভাবে যেখানে সংখ্যাগুলি সাজানো হয় তখন এটি হওয়া উচিত। আবার, আমরা পরবর্তী বৃহত্তম সংখ্যাটিকে আমাদের ক্রমটির শেষে নিয়ে যাব। অবশ্যই, তার মানে দুটি বৃহত্তম সংখ্যা তাদের সঠিক জায়গায় দাঁড়িয়ে আছে। আবার, সমস্ত উপাদান প্রয়োজনীয় ক্রমানুসারে না হওয়া পর্যন্ত আমরা তাদের জায়গায় ইতিমধ্যে থাকা উপাদানগুলিকে বাদ দিয়ে অনুক্রমের উপর দিয়ে পাস করি। জাভা কোডে বুদ্বুদ সাজানোর পদ্ধতিটি কীভাবে প্রয়োগ করা হয় তা একবার দেখে নেওয়া যাক:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
আপনি দেখতে পাচ্ছেন, এখানে জটিল কিছু নেই। সবকিছুই দুর্দান্ত বলে মনে হচ্ছে এবং এটি একটি ত্রুটির জন্য না হলে হবে — বুদ্বুদ সাজানোর খুব, খুব ধীর। এটির সময় জটিলতা হল O(N²), যেহেতু আমাদের নেস্টেড লুপ রয়েছে। উপাদানগুলির উপর বাইরের লুপ N বার সঞ্চালিত হয়। অভ্যন্তরীণ লুপটিও N বার কার্যকর করা হয়। ফলস্বরূপ, আমরা N*N, বা N², পুনরাবৃত্তি পাই।
নির্বাচন বাছাই
এই অ্যালগরিদম বুদবুদ সাজানোর অনুরূপ, কিন্তু এটি একটু দ্রুত কাজ করে। আবার, উদাহরণ হিসাবে, আসুন সংখ্যাগুলির একটি ক্রম নেওয়া যাক যা আমরা আরোহী ক্রমে সাজাতে চাই। এই অ্যালগরিদমের সারমর্ম হল সমস্ত সংখ্যার মাধ্যমে ক্রমানুসারে পুনরাবৃত্তি করা এবং সবচেয়ে ছোট উপাদানটি নির্বাচন করা, যা আমরা গ্রহণ করি এবং বামদিকের উপাদান (0 তম উপাদান) দিয়ে অদলবদল করি। এখানে আমাদের বুদবুদ সাজানোর মতো পরিস্থিতি রয়েছে, তবে এই ক্ষেত্রে আমাদের সাজানো উপাদানটি সবচেয়ে ছোট হবে। অতএব, উপাদানগুলির মধ্য দিয়ে পরবর্তী পাসটি সূচী 1 সহ উপাদান থেকে শুরু হবে৷ সমস্ত উপাদানগুলি সাজানো না হওয়া পর্যন্ত আমরা এই পাসগুলি পুনরাবৃত্তি করব৷ জাভাতে বাস্তবায়ন:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
এই অ্যালগরিদমটি বুদ্বুদ সাজানোর চেয়ে উচ্চতর, কারণ এখানে প্রয়োজনীয় স্থানান্তরের সংখ্যা O(N²) থেকে O(N) এ হ্রাস করা হয়েছে। আমরা পুরো তালিকার মাধ্যমে একটি উপাদান চালাচ্ছি না, তবে তুলনার সংখ্যা এখনও O(N²)।
সন্নিবেশ বাছাই
আমরা আরও একটি সংখ্যা ক্রম বিবেচনা করি যা আমরা আরোহী ক্রমে সাজাতে চাই। এই অ্যালগরিদমটি একটি মার্কার স্থাপন করে, যেখানে মার্কারের বাম দিকের সমস্ত উপাদান ইতিমধ্যেই নিজেদের মধ্যে আংশিকভাবে সাজানো থাকে। অ্যালগরিদমের প্রতিটি ধাপে, উপাদানগুলির মধ্যে একটি নির্বাচন করা হবে এবং আংশিকভাবে সাজানো ক্রমানুসারে পছন্দসই অবস্থানে স্থাপন করা হবে। এইভাবে, সমস্ত উপাদান পরীক্ষা করা না হওয়া পর্যন্ত বাছাই করা অংশটি বৃদ্ধি পাবে। আপনি কি ভাবছেন যে আপনি কীভাবে ইতিমধ্যে সাজানো উপাদানগুলির উপসেট পাবেন এবং কীভাবে আমরা চিহ্নিত করব কোথায় চিহ্নিত করব? কিন্তু প্রথম উপাদান নিয়ে গঠিত অ্যারে ইতিমধ্যেই সাজানো হয়েছে, তাই না? আসুন জাভাতে বাস্তবায়নের দিকে নজর দেওয়া যাক:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
এই ধরণের বাছাই উপরে বর্ণিতগুলির চেয়ে উচ্চতর, কারণ এটির একই O(N²) চলমান সময় থাকা সত্ত্বেও, এই অ্যালগরিদমটি বুদ্বুদ সাজানোর চেয়ে দ্বিগুণ দ্রুত এবং নির্বাচন সাজানোর চেয়ে কিছুটা দ্রুত।
শেল সাজানোর
এই সাজানোর মূলত একটি পরিবর্তিত সন্নিবেশ সাজানোর. আমি কি সম্পর্কে কথা বলছি? এর আগে প্রথম জিনিস করা যাক. আমাদের প্রথমে একটি ব্যবধান বেছে নিতে হবে। এই পছন্দ করার জন্য অনেক পন্থা আছে। আমরা এই সম্পর্কে খুব বিস্তারিত যেতে হবে না. আসুন আমাদের অ্যারেকে অর্ধেক ভাগ করি এবং কিছু সংখ্যা পাই - এটি আমাদের ব্যবধান হবে। সুতরাং, যদি আমাদের অ্যারেতে 9টি উপাদান থাকে, তাহলে আমাদের ব্যবধান হবে 9/2 = 4.5। আমরা ভগ্নাংশটি বাতিল করে 4 পাই, যেহেতু অ্যারে সূচকগুলি কেবলমাত্র পূর্ণসংখ্যা হতে পারে। আমরা আমাদের গ্রুপ গঠনের জন্য এই ব্যবধান ব্যবহার করব। যদি একটি উপাদানের সূচক 0 থাকে, তবে তার গ্রুপের পরবর্তী উপাদানটির সূচকটি 0+4, অর্থাৎ, 4। তৃতীয় উপাদানটির সূচক 4+4, চতুর্থটি - 8+4, ইত্যাদি থাকবে। দ্বিতীয় গ্রুপে, প্রথম উপাদান হবে 1,5,9... তৃতীয় এবং চতুর্থ গ্রুপে, পরিস্থিতি একই হবে। ফলে, নম্বর অ্যারে {6,3,8,8,6,9,4,11,1} থেকে আমরা চারটি গ্রুপ পাই: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} তারা সাধারণ অ্যারেতে তাদের জায়গাগুলি ধরে রাখে, কিন্তু আমরা একই গ্রুপের সদস্য হিসাবে চিহ্নিত করেছি: {6,3,8,8,6,9,4,11,1} পরবর্তী, সন্নিবেশ এই গোষ্ঠীগুলিতে সাজানোর প্রয়োগ করা হয়, এবং তারপরে সেগুলি এইরকম দেখায়: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} সাধারণ অ্যারেতে, গোষ্ঠীগুলির দ্বারা দখলকৃত কক্ষগুলি একই থাকবে, তবে তাদের অভ্যন্তরীণ ক্রম পরিবর্তন হবে, উপরের গোষ্ঠীগুলির ক্রম অনুসারে: {1,3,4,8,6,9,8,11,6} অ্যারে পরিণত হয়েছে একটু বেশি অর্ডার, তাই না? পরবর্তী ব্যবধানকে 2 দ্বারা ভাগ করা হবে: 4/2 = 2 আমাদের দুটি গ্রুপ আছে: I — {1,4,6,8,6} II — {3,8,9,11} সাধারণ অ্যারেতে, আমাদের আছে : {1,3,4,8,6,9,8,11,6} আমরা উভয় গ্রুপে সন্নিবেশ সাজানোর অ্যালগরিদম চালাই এবং এই অ্যারেটি পাই: {1,3,4,8,6,9,6, 11, 8} এখন আমাদের অ্যারে প্রায় সাজানো হয়েছে। আমাদের অ্যালগরিদমের একটি চূড়ান্ত পুনরাবৃত্তি করতে হবে: আমরা ব্যবধানকে 2: 2/2 = 1 দ্বারা ভাগ করি। আমরা পুরো অ্যারে নিয়ে গঠিত একটি গ্রুপ পাই: {1,3,4,8,6,9,6,11 ,8} সন্নিবেশ সাজানোর অ্যালগরিদম চালালে, আমরা পাই: {1,3,4,6,6,8,8,9,11} চলুন এক নজরে দেখে নেওয়া যাক কিভাবে আমরা জাভা কোডে এই সাজানোকে প্রাণবন্ত করতে পারি:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
এই মুহুর্তে, Shellsort এর কর্মক্ষমতা চিহ্নিত করা সহজ নয়, কারণ বিভিন্ন পরিস্থিতিতে ফলাফল ভিন্ন হয়। পরীক্ষামূলক অনুমান O(N 3/2 ) থেকে O(N 7/6 ) পর্যন্ত।
কুইকসর্ট
এটি সবচেয়ে জনপ্রিয় অ্যালগরিদমগুলির মধ্যে একটি, তাই এটির প্রতি বিশেষ মনোযোগ দেওয়া মূল্যবান। এই অ্যালগরিদমের সারাংশ হল যে একটি পিভট উপাদান উপাদানগুলির একটি তালিকায় নির্বাচিত হয়। আমরা পিভট উপাদানের সাথে সম্পর্কিত অন্যান্য সমস্ত উপাদান বাছাই করি। পিভট উপাদানের চেয়ে কম মানগুলি বাম দিকে রয়েছে৷ এর চেয়ে বড় মান ডানদিকে রয়েছে। এর পরে, পিভট উপাদানগুলিও ডান এবং বাম অংশে নির্বাচন করা হয় এবং একই জিনিস ঘটে: মানগুলি এই উপাদানগুলির সাথে সাপেক্ষে সাজানো হয়। তারপরে নতুন গঠিত অংশগুলিতে পিভট উপাদানগুলি নির্বাচন করা হয়, এবং যতক্ষণ না আমরা একটি সাজানো ক্রম না পাই। এই অ্যালগরিদমের নিম্নলিখিত জাভা বাস্তবায়ন পুনরাবৃত্তি ব্যবহার করে:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
নিঃসন্দেহে, কুইকসোর্ট অ্যালগরিদম সবচেয়ে জনপ্রিয়, যেহেতু বেশিরভাগ পরিস্থিতিতে এটি অন্যদের তুলনায় দ্রুত চলে। এর সময় জটিলতা হল O(N*logN)।
মার্জ সাজান
এই সাজানোরও জনপ্রিয়। এটি অনেক অ্যালগরিদমের মধ্যে একটি যা "বিভক্ত করুন এবং জয় করুন" নীতির উপর নির্ভর করে। এই জাতীয় অ্যালগরিদম প্রথমে সমস্যাটিকে পরিচালনাযোগ্য অংশে ভাগ করে (কুইকসর্ট এই জাতীয় অ্যালগরিদমের আরেকটি উদাহরণ)। তাই এই অ্যালগরিদম সারাংশ কি?
বিভক্ত করা:
অ্যারেটি প্রায় একই আকারের দুটি অংশে বিভক্ত। এই দুটি অংশের প্রত্যেকটি আরও দুটি ভাগে বিভক্ত, এবং যতক্ষণ না ক্ষুদ্রতম সম্ভাব্য অবিভাজ্য অংশ অবশিষ্ট থাকে। আমাদের কাছে ক্ষুদ্রতম অবিভাজ্য অংশ থাকে যখন প্রতিটি অ্যারের একটি উপাদান থাকে, যেমন একটি অ্যারে যা ইতিমধ্যে সাজানো থাকে।
জয়:
এখানেই আমরা সেই প্রক্রিয়া শুরু করি যা অ্যালগরিদমকে এর নাম দিয়েছে: মার্জ। এটি করার জন্য, আমরা দুটি ফলস্বরূপ সাজানো অ্যারে নিয়ে যাই এবং সেগুলিকে একটিতে মার্জ করি। এই ক্ষেত্রে, দুটি অ্যারের প্রথম উপাদানগুলির মধ্যে সবচেয়ে ছোটটি ফলস্বরূপ অ্যারেতে লেখা হয়। এই দুটি অ্যারের সমস্ত উপাদান কপি করা না হওয়া পর্যন্ত এই অপারেশনটি পুনরাবৃত্তি করা হয়। অর্থাৎ, যদি আমাদের দুটি ন্যূনতম অ্যারে থাকে {6} এবং {4}, আমরা তাদের মান তুলনা করি এবং এই একত্রিত ফলাফল তৈরি করি: {4,6}। যদি আমরা {4,6} এবং {2,8} অ্যারে সাজিয়ে থাকি, তাহলে আমরা প্রথমে 4 এবং 2 মানগুলি তুলনা করি এবং তারপরে আমরা ফলাফলের অ্যারেতে 2 লিখি। এর পরে, 4 এবং 8 তুলনা করা হবে, এবং আমরা 4 লিখব। অবশেষে, 6 এবং 8 তুলনা করা হবে। তদনুসারে, আমরা 6 লিখব, এবং শুধুমাত্র তার পরে আমরা 8 লিখব। ফলস্বরূপ, আমরা নিম্নলিখিত মার্জড অ্যারে পাব: {2,4,6,8}। জাভা কোডে এটি কেমন দেখাবে? এই অ্যালগরিদম চালানোর জন্য, আমাদের জন্য পুনরাবৃত্তি ব্যবহার করা সুবিধাজনক হবে:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
দ্রুত সাজানোর মতো, আমরা পুনরাবৃত্ত পদ্ধতিটিকে একটি মধ্যবর্তী পদ্ধতিতে স্থানান্তরিত করি যাতে ব্যবহারকারীকে কেবল সাজানোর জন্য অ্যারে সরবরাহ করতে হয় এবং কোনও অতিরিক্ত ডিফল্ট আর্গুমেন্ট দেওয়ার বিষয়ে চিন্তা করতে হয় না। এই অ্যালগরিদমের সাথে কুইকসর্টের মিল রয়েছে এবং আশ্চর্যজনকভাবে এটি কার্যকর করার গতি একই: O(N*logN)।
2. লোভী অ্যালগরিদম
একটি লোভী অ্যালগরিদম হল একটি পদ্ধতি যেখানে প্রতিটি পর্যায়ে স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত নেওয়া হয়, এই ধারণার সাথে যে চূড়ান্ত সমাধানটিও সর্বোত্তম হবে। "অনুকূল" সমাধান হবে এমন একটি যা কোনো নির্দিষ্ট ধাপ/পর্যায়ে সবচেয়ে সুস্পষ্ট এবং তাৎক্ষণিক সুবিধা প্রদান করে। এই অ্যালগরিদমটি অন্বেষণ করতে, আসুন একটি মোটামুটি সাধারণ সমস্যা ধরা যাক - ন্যাপস্যাক সমস্যা। এক মুহুর্তের জন্য ভান করুন যে আপনি একজন চোর। আপনি একটি ন্যাপস্যাক (ব্যাকপ্যাক) নিয়ে রাতে একটি দোকানে প্রবেশ করেছেন। আপনার সামনে বেশ কিছু মালামাল রয়েছে যা আপনি চুরি করতে পারেন। কিন্তু একই সময়ে, আপনার ন্যাপস্যাকের ক্ষমতা সীমিত। এটি 30 ইউনিটের বেশি ওজন বহন করতে পারে না। আপনি ব্যাকপ্যাকের মধ্যে ফিট করা জিনিসগুলির সবচেয়ে মূল্যবান সেটটিও বহন করতে চান। আপনার ব্যাগে কী রাখবেন তা আপনি কীভাবে নির্ধারণ করবেন? তাই,
সবচেয়ে দামি আইটেমটি বেছে নিন যা এখনও নেওয়া হয়নি।
যদি এটি ন্যাপস্যাকে ফিট করে তবে এটি রাখুন। যদি না হয়, তাহলে এটি ছেড়ে দিন।
আমরা কি ইতিমধ্যে সবকিছু চুরি করেছি? যদি না হয়, আমরা ধাপ 1 এ ফিরে আসি। যদি হ্যাঁ, তাহলে আমরা দোকান থেকে দ্রুত বের হয়ে যাই, যেহেতু আমরা যা করতে এসেছি তা সম্পন্ন করেছি।
চলুন এটি তাকান, কিন্তু জাভা. এইভাবে আইটেম ক্লাস দেখতে হবে:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
এখানে বিশেষ কিছু নেই: তিনটি ক্ষেত্র (নাম, ওজন, মান) যা আইটেমের বৈশিষ্ট্যগুলিকে সংজ্ঞায়িত করে। এছাড়াও, আপনি দেখতে পাচ্ছেন, তুলনামূলক ইন্টারফেসটি প্রয়োগ করা হয়েছে যাতে আমরা আমাদের আইটেমগুলিকে মূল্য অনুসারে সাজাতে পারি। এর পরে, আমরা ব্যাগ শ্রেণীটি দেখব, যা আমাদের ন্যাপস্যাকের প্রতিনিধিত্ব করে:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight হল আমাদের ব্যাকপ্যাকের ক্ষমতা, যা সেট করা হয় যখন আমরা একটি বস্তু তৈরি করি;
আইটেম আমাদের ব্যাকপ্যাক বস্তুর প্রতিনিধিত্ব করে;
currentWeight , currentValue — এই ক্ষেত্রগুলি ব্যাকপ্যাকের সমস্ত আইটেমের বর্তমান ওজন এবং মান সংরক্ষণ করে, যা আমরা যখন addItem পদ্ধতিতে একটি নতুন আইটেম যোগ করি তখন আমরা বৃদ্ধি করি।
যাইহোক, চলুন এখন সেই ক্লাসে যাই যেখানে সমস্ত অ্যাকশন হয়:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
প্রথমত, আমরা আইটেমগুলির একটি তালিকা তৈরি করি এবং এটি বাছাই করি। আমরা 30-ইউনিট ক্ষমতা সহ একটি ব্যাগ বস্তু তৈরি করি। এরপরে, আমরা ফিলব্যাকপ্যাক পদ্ধতিতে আইটেম এবং ব্যাগ অবজেক্ট পাস করি, যা আমাদের লোভী অ্যালগরিদম অনুযায়ী ন্যাপস্যাক পূরণ করে:
এটি বেশ সহজ: আমরা খরচ অনুসারে সাজানো আইটেমগুলির একটি তালিকার মধ্য দিয়ে যেতে শুরু করি এবং যদি এর ক্ষমতা অনুমতি দেয় তবে সেগুলি ব্যাগে রাখি। যদি পর্যাপ্ত জায়গা না থাকে, তাহলে আইটেমটি বাদ দেওয়া হবে এবং আমরা তালিকার শেষ পর্যন্ত না পৌঁছা পর্যন্ত বাকি আইটেমগুলি অতিক্রম করতে থাকব। একবার আমরা মেইন চালালে, এখানে কনসোল আউটপুট আমরা পাব:
ন্যাপস্যাকের ওজন 29। ন্যাপস্যাকের মোট আইটেমের মূল্য 3700
এটি একটি লোভী অ্যালগরিদমের একটি উদাহরণ: প্রতিটি ধাপে, একটি স্থানীয়ভাবে সর্বোত্তম সমাধান নির্বাচন করা হয় এবং শেষ পর্যন্ত, আপনি একটি বিশ্বব্যাপী সর্বোত্তম সমাধান পান৷ আমাদের ক্ষেত্রে, সেরা বিকল্প হল সবচেয়ে ব্যয়বহুল আইটেম। কিন্তু এই সেরা সমাধান? আপনি কি মনে করেন না যে আমাদের ব্যাকপ্যাকটি এমন আইটেম দিয়ে পূরণ করার জন্য আমাদের সমাধানকে কিছুটা উন্নত করা সম্ভব যেগুলির মোট মূল্য আরও বেশি? চলুন দেখে নেওয়া যাক কিভাবে এটি করা যায়।
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
এখানে আমরা প্রথমে প্রতিটি আইটেমের জন্য মান-টু-ওজন অনুপাত গণনা করি। এটি আমাদের একটি প্রদত্ত আইটেমের প্রতিটি ইউনিটের মান বলে। এবং তারপরে আমরা আমাদের আইটেমগুলি বাছাই করতে এবং সেগুলিকে আমাদের ব্যাগে যুক্ত করতে এই অনুপাতগুলি ব্যবহার করি। চলুন নিম্নলিখিত রান করা যাক:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
আমরা এই কনসোল আউটপুট পাই:
ন্যাপস্যাকের ওজন 29। ন্যাপস্যাকের মোট আইটেমের দাম 4150
একটু ভালো, তাই না? লোভী অ্যালগরিদম প্রতিটি পদক্ষেপে একটি স্থানীয়ভাবে সর্বোত্তম পছন্দ করে, আশা করে যে চূড়ান্ত সমাধানটিও সর্বোত্তম হবে। এই অনুমান সবসময় বৈধ নয়, কিন্তু অনেক কাজের জন্য, লোভী অ্যালগরিদম একটি সর্বোত্তম চূড়ান্ত সমাধান দেয়। এই অ্যালগরিদমের সময় জটিলতা হল O(N)। বেশ ভালো, হাহ?
এবং যেহেতু আপনি এই ওয়েবসাইটে আছেন, আমি এতটা সাহসী হব যে আপনি জাভাতে লিখছেন। এই কারণেই আজ আমি আপনাকে কিছু মৌলিক অ্যালগরিদম এবং জাভাতে কীভাবে প্রয়োগ করতে হয় তার নির্দিষ্ট উদাহরণগুলির সাথে নিজেকে পরিচিত করার পরামর্শ দিচ্ছি। "কিছু" দ্বারা, আমি বলতে চাচ্ছি:
GO TO FULL VERSION