Ang mga proyekto sa pag-unlad ay gumagamit ng iba't ibang mga algorithm nang mas madalas kaysa sa iniisip mo. Halimbawa, ipagpalagay na kailangan nating pag-uri-uriin ang ilang data ayon sa ilang mga parameter (column) para makapag-navigate tayo sa data nang walang labis na pagsisikap. Kaya't hindi magiging kakaiba para sa isang tagapanayam sa trabaho na magtanong sa iyo tungkol sa isang tiyak na pangunahing algorithm at marahil ay bigyan ang gawain ng pagpapatupad nito gamit ang code. At dahil ikaw ay nasa website na ito, ako ay magiging matapang na ipagpalagay na ikaw ay nagsusulat sa Java. Iyon ang dahilan kung bakit ngayon iminumungkahi ko na pamilyar ka sa ilang mga pangunahing algorithm at sa mga partikular na halimbawa kung paano ipatupad ang mga ito sa Java. Sa pamamagitan ng "ilan", ang ibig kong sabihin ay:
Pangkalahatang-ideya ng mga algorithm ng pag-uuri ng array:
pag-uuri ng bula,
uri ng pagpili,
insertion sort,
Pag-uuri ng shell,
quicksort,
sumanib-uuri,
Mga sakim na algorithm
Mga algorithm sa paghahanap ng landas
malalim-unang paghahanap
lapad-unang paghahanap
Algorithm ng Pinakamaikling Daan ng Dijkstra
Buweno, nang walang karagdagang ado, bumaba tayo sa negosyo.
1. Pangkalahatang-ideya ng mga algorithm ng pag-uuri
Bubble sort
Ang algorithm ng pag-uuri na ito ay kilala lalo na sa pagiging simple nito, ngunit isa rin ito sa pinakamabagal. Bilang halimbawa, isaalang-alang natin ang isang bubble sort para sa mga numero sa pataas na pagkakasunud-sunod. Isipin natin ang isang random na pagkakasunud-sunod ng mga numero. Gagawin namin ang mga sumusunod na hakbang sa mga numerong ito, simula sa simula ng pagkakasunud-sunod:
ihambing ang dalawang numero;
kung ang numero sa kaliwa ay mas malaki, pagkatapos ay palitan ang mga ito;
ilipat ang isang posisyon sa kanan.
Pagkatapos isagawa ang mga hakbang na ito sa buong pagkakasunud-sunod, makikita namin na ang pinakamalaking bilang ay nasa dulo ng aming serye ng mga numero. Pagkatapos ay gumawa kami ng isa pang pagpasa sa pagkakasunud-sunod, na isinasagawa ang eksaktong parehong mga hakbang tulad ng nasa itaas. Ngunit sa pagkakataong ito ay hindi na namin isasama ang huling elemento ng listahan, dahil ito ang pinakamalaking bilang at eksakto kung saan ito dapat kapag pinagbukud-bukod ang mga numero. Muli, ililipat namin ang susunod na pinakamalaking numero sa dulo ng aming sequence. Siyempre, nangangahulugan iyon na ang dalawang pinakamalaking numero ay nakatayo sa kanilang mga tamang lugar. Muli, gumawa kami ng mga pass sa pagkakasunud-sunod, hindi kasama ang mga elemento na nasa kanilang mga lugar, hanggang sa ang lahat ng mga elemento ay nasa kinakailangang pagkakasunud-sunod. Tingnan natin kung paano ipinapatupad ang bubble sort sa Java code:
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;
}
}
}
}
}
Tulad ng nakikita mo, walang kumplikado dito. Ang lahat ay tila napakahusay at ito ay magiging kung hindi para sa isang pagkukulang — bubble sort ay napaka, napakabagal. Ang pagiging kumplikado ng oras ay O(N²), dahil mayroon kaming mga nested na loop. Ang panlabas na loop sa ibabaw ng mga elemento ay ginaganap N beses. Ang panloob na loop ay pinaandar din ng N beses. Bilang resulta, nakakakuha kami ng N*N, o N², mga pag-ulit.
Pag-uuri ng pagpili
Ang algorithm na ito ay katulad ng bubble sort, ngunit ito ay gumagana nang kaunti nang mas mabilis. Muli, bilang isang halimbawa, kumuha tayo ng isang pagkakasunud-sunod ng mga numero na nais nating ayusin sa pataas na pagkakasunud-sunod. Ang kakanyahan ng algorithm na ito ay ang sunud-sunod na pag-ulit sa lahat ng mga numero at piliin ang pinakamaliit na elemento, na kinukuha namin at pinapalitan sa pinakakaliwang elemento (ang ika-0 na elemento). Narito mayroon kaming isang sitwasyon na katulad ng bubble sort, ngunit sa kasong ito ang aming pinagsunod-sunod na elemento ay ang pinakamaliit. Samakatuwid, ang susunod na pagpasa sa mga elemento ay magsisimula mula sa elementong may index 1. Uulitin namin ang mga pass na ito hanggang sa maiayos ang lahat ng elemento. Pagpapatupad sa 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;
}
}
}
Ang algorithm na ito ay mas mataas kaysa sa bubble sort, dahil dito ang bilang ng mga kinakailangang shift ay nababawasan mula O(N²) hanggang O(N). Hindi kami nagtutulak ng isang elemento sa buong listahan, ngunit ang bilang ng mga paghahambing ay O(N² pa rin).
Pag-uuri ng pagpapasok
Isinasaalang-alang namin ang isa pang pagkakasunud-sunod ng numero na gusto naming ayusin sa pataas na pagkakasunud-sunod. Ang algorithm na ito ay binubuo sa paglalagay ng isang marker, kung saan ang lahat ng mga elemento sa kaliwa ng marker ay bahagyang pinagsunod-sunod sa kanilang mga sarili. Sa bawat hakbang ng algorithm, pipiliin ang isa sa mga elemento at ilalagay sa nais na posisyon sa bahagyang pinagsunod-sunod na pagkakasunud-sunod. Kaya, ang pinagsunod-sunod na bahagi ay lalago hanggang sa masuri ang lahat ng mga elemento. Nagtataka ka ba kung paano mo makukuha ang subset ng mga elemento na pinagsunod-sunod na at kung paano namin tinutukoy kung saan ilalagay ang marker? Ngunit ang array na binubuo ng unang elemento ay nakaayos na, hindi ba? Tingnan natin ang pagpapatupad sa Java:
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
}
}
}
Ang ganitong uri ng pag-uuri ay mas mataas kaysa sa mga inilarawan sa itaas, dahil sa kabila ng katotohanan na mayroon itong parehong oras ng pagpapatakbo ng O(N²), ang algorithm na ito ay dalawang beses na mas mabilis kaysa sa bubble sort at bahagyang mas mabilis kaysa sa selection sort.
Pag-uuri ng shell
Ang uri na ito ay mahalagang binagong insertion sort. Ano bang pinagsasabi ko? Unahin natin ang mga bagay. Kailangan muna nating pumili ng pagitan. Mayroong maraming mga diskarte sa paggawa ng pagpipiliang ito. Hindi na tayo magdetalye tungkol dito. Hatiin natin ang ating array sa kalahati at kumuha ng ilang numero — ito ang magiging agwat natin. Kaya, kung mayroon tayong 9 na elemento sa ating array, ang pagitan natin ay magiging 9/2 = 4.5. Itapon namin ang fractional na bahagi at makakuha ng 4, dahil ang mga indeks ng array ay maaari lamang maging integer. Gagamitin namin ang interval na ito para mabuo ang aming mga grupo. Kung ang isang elemento ay may index 0, kung gayon ang index ng susunod na elemento sa pangkat nito ay 0+4, iyon ay, 4. Ang ikatlong elemento ay magkakaroon ng index 4+4, ang pang-apat — 8+4, at iba pa. Sa pangalawang grupo, ang unang elemento ay magiging 1,5,9... Sa ikatlo at ikaapat na grupo, ang sitwasyon ay magiging pareho. Ang resulta, mula sa array ng numero {6,3,8,8,6,9,4,11,1} nakakakuha tayo ng apat na grupo: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Pinapanatili nila ang kanilang mga lugar sa pangkalahatang hanay, ngunit minarkahan namin bilang mga miyembro ng parehong grupo: {6,3,8,8,6,9,4,11,1} Susunod, pagpasok ang sort ay inilapat sa mga pangkat na ito, at pagkatapos ay ganito ang hitsura nila: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Sa pangkalahatang hanay, ang ang mga cell na inookupahan ng mga pangkat ay mananatiling pareho, ngunit ang kanilang panloob na pagkakasunud-sunod ay magbabago, ayon sa pagkakasunud-sunod ng mga pangkat sa itaas: {1,3,4,8,6,9,8,11,6} Ang array ay naging isang konting order pa, di ba? Ang susunod na pagitan ay hahatiin ng 2: 4/2 = 2 Mayroon kaming dalawang grupo: I — {1,4,6,8,6} II — {3,8,9,11} Sa pangkalahatang hanay, mayroon kaming : {1,3,4,8,6,9,8,11,6} Pinapatakbo namin ang insertion sort algorithm sa parehong grupo, at nakuha ang array na ito: {1,3,4,8,6,9,6, 11, 8} Ngayon ang aming array ay halos pinagsunod-sunod. Kailangan naming magsagawa ng panghuling pag-ulit ng algorithm: hinahati namin ang pagitan sa 2: 2/2 = 1. Kumuha kami ng pangkat na binubuo ng buong array: {1,3,4,8,6,9,6,11 ,8} Sa pagpapatakbo ng insertion sort algorithm doon, makukuha natin ang: {1,3,4,6,6,8,8,9,11} Tingnan natin kung paano natin mabubuhay ang ganitong uri sa Java code:
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
}
}
}
Sa ngayon, ang pagganap ng Shellsort ay hindi madaling makilala, dahil ang mga resulta ay naiiba sa iba't ibang mga sitwasyon. Ang mga pang-eksperimentong pagtatantya ay mula sa O(N 3/2 ) hanggang O(N 7/6 ).
Quicksort
Ito ay isa sa mga pinakasikat na algorithm, kaya ito ay nagkakahalaga ng pagbibigay ng espesyal na pansin. Ang diwa ng algorithm na ito ay ang isang elemento ng pivot ay pinili sa isang listahan ng mga elemento. Inuuri namin ang lahat ng iba pang elemento na nauugnay sa elemento ng pivot. Nasa kaliwa ang mga value na mas mababa sa pivot element. Mga halagang mas malaki kaysa sa nasa kanan. Susunod, pinipili din ang mga elemento ng pivot sa kanan at kaliwang bahagi, at ganoon din ang nangyayari: ang mga halaga ay pinagsunod-sunod na may kaugnayan sa mga elementong ito. Pagkatapos ay pinipili ang mga elemento ng pivot sa mga bagong nabuong bahagi, at iba pa hanggang sa makakuha tayo ng pinagsunod-sunod na pagkakasunud-sunod. Ang sumusunod na pagpapatupad ng Java ng algorithm na ito ay gumagamit ng recursion:
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);
}
}
Walang alinlangan, ang quicksort algorithm ay ang pinakasikat, dahil sa karamihan ng mga sitwasyon ito ay tumatakbo nang mas mabilis kaysa sa iba. Ang pagiging kumplikado ng oras nito ay O(N*logN).
Sumanib-uuri
Ang ganitong uri ay sikat din. Ito ay isa sa maraming mga algorithm na umaasa sa prinsipyo ng "divide and conquer". Ang ganitong mga algorithm ay unang hatiin ang problema sa mga napapamahalaang bahagi (ang quicksort ay isa pang halimbawa ng naturang algorithm). Kaya ano ang diwa ng algorithm na ito?
hatiin:
Ang array ay nahahati sa dalawang bahagi na humigit-kumulang sa parehong laki. Ang bawat isa sa dalawang bahaging ito ay nahahati sa dalawa pa, at iba pa hanggang sa mananatili ang pinakamaliit na posibleng hindi mahahati na mga bahagi. Mayroon kaming pinakamaliit na hindi mahahati na bahagi kapag ang bawat array ay may isang elemento, ibig sabihin, isang array na nakaayos na.
lupigin:
Dito natin sinisimulan ang proseso na nagbigay sa algorithm ng pangalan nito: merge. Upang gawin ito, kukunin namin ang dalawang resultang pinagsunod-sunod na mga array at pagsamahin ang mga ito sa isa. Sa kasong ito, ang pinakamaliit sa mga unang elemento ng dalawang array ay nakasulat sa resultang array. Ang operasyong ito ay paulit-ulit hanggang ang lahat ng elemento sa dalawang array na ito ay makopya. Iyon ay, kung mayroon kaming dalawang minimal na array {6} at {4}, inihahambing namin ang kanilang mga halaga at bubuo ng pinagsamang resultang ito: {4,6}. Kung pinagbukud-bukod namin ang mga array {4,6} at {2,8}, inihambing muna namin ang mga value 4 at 2, at pagkatapos ay isusulat namin ang 2 sa resultang array. Pagkatapos nito, ihahambing ang 4 at 8, at isusulat natin ang 4. Sa wakas, ang 6 at 8 ay ikukumpara. Alinsunod dito, magsusulat kami ng 6, at pagkatapos lamang nito ay magsusulat kami ng 8. Bilang resulta, nakukuha namin ang sumusunod na pinagsamang array: {2,4,6,8}. Paano ito magiging hitsura sa Java code? Upang patakbuhin ang algorithm na ito, magiging maginhawa para sa amin na gumamit ng recursion:
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;
}
}
Tulad ng sa mabilisang pag-uuri, inililipat namin ang recursive na paraan sa isang intermediate na paraan upang ang user ay kailangan lamang na magbigay ng array para pagbukud-bukurin at hindi na kailangang mag-alala tungkol sa pagbibigay ng anumang karagdagang mga default na argumento. Ang algorithm na ito ay may pagkakatulad sa quicksort, at hindi nakakagulat na ang bilis ng pagpapatupad nito ay pareho: O(N*logN).
2. Mga sakim na algorithm
Ang isang matakaw na algorithm ay isang diskarte kung saan ang mga lokal na pinakamainam na desisyon ay ginagawa sa bawat yugto, na may pag-aakalang magiging pinakamainam din ang panghuling solusyon. Ang "pinakamainam" na solusyon ay ang isa na nag-aalok ng pinaka-halata at agarang benepisyo sa anumang partikular na hakbang/yugto. Upang galugarin ang algorithm na ito, kunin natin ang isang medyo karaniwang problema — ang problema sa knapsack. Magpanggap saglit na magnanakaw ka. Nakapasok ka sa isang tindahan sa gabi na may dalang knapsack (backpack). Sa harap mo ay ilang mga kalakal na maaari mong nakawin. Ngunit sa parehong oras, ang iyong knapsack ay may limitadong kapasidad. Maaari itong magdala ng hindi hihigit sa 30 yunit ng timbang. Gusto mo ring dalhin ang pinakamahalagang hanay ng mga kalakal na kasya sa backpack. Paano mo matukoy kung ano ang ilalagay sa iyong bag? Kaya,
Piliin ang pinakamahal na bagay na hindi pa nakukuha.
Kung kasya ito sa knapsack, ilagay ito. Kung hindi, pagkatapos ay iwanan ito.
Ninakaw na ba natin ang lahat? Kung hindi, babalik tayo sa hakbang 1. Kung oo, pagkatapos ay mabilis tayong umalis sa tindahan, dahil nagawa na natin ang dapat nating gawin.
Tingnan natin ito, ngunit sa Java. Ganito ang magiging hitsura ng klase ng Item:
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;
}
}
Walang espesyal dito: tatlong field (pangalan, timbang, halaga) na tumutukoy sa mga katangian ng item. Gayundin, tulad ng nakikita mo, ipinatupad ang Comparable interface upang payagan kaming pagbukud-bukurin ang aming Mga Item ayon sa presyo. Susunod, titingnan natin ang klase ng Bag, na kumakatawan sa aming knapsack:
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();
}
}
ang maxWeight ay ang kapasidad ng aming backpack, na itinakda kapag lumikha kami ng isang bagay;
ang mga item ay kumakatawan sa mga bagay sa aming backpack;
currentWeight , currentValue — ang mga field na ito ay nag-iimbak ng kasalukuyang timbang at halaga ng lahat ng item sa backpack, na tinataasan namin kapag nagdagdag kami ng bagong item sa paraan ng addItem.
Anyway, pumunta na tayo sa klase kung saan nagaganap ang lahat ng aksyon:
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());
}
}
Una, gumawa kami ng isang listahan ng mga item at pag-uri-uriin ito. Lumilikha kami ng isang bagay ng bag na may kapasidad na 30 yunit. Susunod, ipinapasa namin ang mga item at bagay sa bag sa paraan ng fillBackpack, na pumupuno sa knapsack ayon sa aming matakaw na algorithm:
Ito ay medyo simple: magsisimula kaming dumaan sa isang listahan ng mga item na pinagsunod-sunod ayon sa gastos at ilagay ang mga ito sa bag kung pinapayagan ang kapasidad nito. Kung walang sapat na espasyo, lalaktawan ang item at magpapatuloy kami sa pagtawid sa iba pang mga item hanggang sa maabot namin ang dulo ng listahan. Sa sandaling tumakbo kami sa pangunahing, narito ang output ng console na makukuha namin:
Ang timbang ng knapsack ay 29. Ang kabuuang halaga ng mga item sa knapsack ay 3700
Ito ay isang halimbawa ng isang matakaw na algorithm: sa bawat hakbang, isang lokal na pinakamainam na solusyon ang pipiliin, at sa huli, makakakuha ka ng pandaigdigang pinakamainam na solusyon. Sa aming kaso, ang pinakamagandang opsyon ay ang pinakamahal na item. Ngunit ito ba ang pinakamahusay na solusyon? Sa palagay mo, hindi ba posible na pagbutihin ang aming solusyon nang bahagya upang mapuno ang aming backpack ng mga item na may mas malaking kabuuang halaga? Tingnan natin kung paano ito magagawa.
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());
}
}
}
Dito muna namin kinakalkula ang ratio ng value-to-weight para sa bawat item. Sinasabi nito sa amin ang halaga ng bawat unit ng isang naibigay na item. At pagkatapos ay ginagamit namin ang mga ratio na ito upang pagbukud-bukurin ang aming mga item at idagdag ang mga ito sa aming bag. Patakbuhin natin ang sumusunod:
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());
Nakukuha namin ang output ng console na ito:
Ang bigat ng knapsack ay 29. Ang kabuuang halaga ng mga item sa knapsack ay 4150
Medyo mas maganda, di ba? Ang matakaw na algorithm ay gumagawa ng lokal na pinakamainam na pagpipilian sa bawat hakbang, umaasa na ang panghuling solusyon ay magiging pinakamainam din. Ang pagpapalagay na ito ay hindi palaging wasto, ngunit para sa maraming mga gawain, ang mga matakaw na algorithm ay nagbubunga ng pinakamainam na panghuling solusyon. Ang pagiging kumplikado ng oras ng algorithm na ito ay O(N). Medyo maganda, ha?
At dahil ikaw ay nasa website na ito, ako ay magiging matapang na ipagpalagay na ikaw ay nagsusulat sa Java. Iyon ang dahilan kung bakit ngayon iminumungkahi ko na pamilyar ka sa ilang mga pangunahing algorithm at sa mga partikular na halimbawa kung paano ipatupad ang mga ito sa Java. Sa pamamagitan ng "ilan", ang ibig kong sabihin ay:
GO TO FULL VERSION