डेव्हलपमेंट प्रोजेक्ट्स तुम्ही विचार करता त्यापेक्षा जास्त वेळा विविध अल्गोरिदम वापरतात. उदाहरणार्थ, समजा आम्हाला काही डेटा काही पॅरामीटर्स (स्तंभ) नुसार क्रमवारी लावायचा आहे जेणेकरून आम्ही जास्त प्रयत्न न करता डेटावर नेव्हिगेट करू शकतो. त्यामुळे नोकरीसाठी मुलाखत घेणाऱ्या व्यक्तीने तुम्हाला विशिष्ट मूलभूत अल्गोरिदमबद्दल विचारणे आणि कदाचित कोड वापरून त्याची अंमलबजावणी करण्याचे काम देणे अजिबात विचित्र होणार नाही. आणि तुम्ही या वेबसाईटवर असल्याने, तुम्ही जावामध्ये लिहित आहात असे गृहीत धरण्यासाठी मी इतके धाडसी होईल. म्हणूनच आज मी सुचवितो की तुम्ही स्वतःला काही मूलभूत अल्गोरिदम आणि Java मध्ये ते कसे अंमलात आणायचे याच्या विशिष्ट उदाहरणांसह परिचित व्हा. "काही" द्वारे, म्हणजे:
अॅरे सॉर्टिंग अल्गोरिदमचे विहंगावलोकन:
बबल क्रमवारी,
निवड क्रमवारी,
प्रवेश क्रमवारी,
शेल क्रमवारी,
द्रुत क्रम,
क्रमवारी विलीन करा,
लोभी अल्गोरिदम
पाथफाइंडिंग अल्गोरिदम
खोली-प्रथम शोध
रुंदी-प्रथम शोध
डिजक्स्ट्राचा शॉर्टेस्ट पाथ फर्स्ट अल्गोरिदम
बरं, आणखी अडचण न ठेवता, चला व्यवसायात उतरूया.
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 सह घटकापासून सुरू होईल. सर्व घटकांची क्रमवारी लावले जाईपर्यंत आम्ही हे पास पुन्हा करू. Java मध्ये अंमलबजावणी:
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 आणि असेच असेल. दुसऱ्या गटात, पहिला घटक १,५,९ असेल... तिसऱ्या आणि चौथ्या गटात परिस्थिती सारखीच असेल. परिणामी, नंबर अॅरे {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
}
}
}
याक्षणी, शेलसोर्टची कामगिरी वैशिष्ट्यीकृत करणे सोपे नाही, कारण वेगवेगळ्या परिस्थितींमध्ये परिणाम भिन्न असतात. प्रायोगिक अंदाज O(N 3/2 ) ते O(N 7/6 ) पर्यंत आहेत.
Quicksort
हे सर्वात लोकप्रिय अल्गोरिदमपैकी एक आहे, म्हणून त्यावर विशेष लक्ष देणे योग्य आहे. या अल्गोरिदमचा सारांश असा आहे की घटकांच्या सूचीमध्ये एक मुख्य घटक निवडला जातो. आम्ही पिव्होट घटकाशी संबंधित इतर सर्व घटकांची क्रमवारी लावतो. मुख्य घटकापेक्षा कमी मूल्ये डावीकडे आहेत. पेक्षा मोठी मूल्ये उजवीकडे आहेत. पुढे, उजव्या आणि डाव्या भागांमध्ये मुख्य घटक देखील निवडले जातात आणि तेच घडते: मूल्ये या घटकांच्या सापेक्ष क्रमवारीत लावली जातात. नंतर नवीन तयार केलेल्या भागांमध्ये पिव्होट घटक निवडले जातात आणि असेच क्रमवारी लावलेले क्रम मिळत नाही. या अल्गोरिदमची खालील Java अंमलबजावणी पुनरावृत्ती वापरते:
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}. हे Java कोडमध्ये कसे दिसेल? हा अल्गोरिदम चालविण्यासाठी, पुनरावृत्ती वापरणे आमच्यासाठी सोयीचे असेल:
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) आहे. तेही चांगले, हं?
आणि तुम्ही या वेबसाईटवर असल्याने, तुम्ही जावामध्ये लिहित आहात असे गृहीत धरण्यासाठी मी इतके धाडसी होईल. म्हणूनच आज मी सुचवितो की तुम्ही स्वतःला काही मूलभूत अल्गोरिदम आणि Java मध्ये ते कसे अंमलात आणायचे याच्या विशिष्ट उदाहरणांसह परिचित व्हा. "काही" द्वारे, म्हणजे:
GO TO FULL VERSION