一個背著背包的小偷闖空門偷東西，他必須趁屋主回來之前把有價值的物品塞進包包內帶走。考慮到小偷自身的行動力，背包能裝的物品總重量有限，小偷要如何選擇物品才能獲得最高的總價值？
MagicLen
MagicLen
內容
分類：演算法
許多人認為身上如果帶太多的零錢會讓行動變得不方便，因此會希望商店店員在找零錢的時候能夠以最少的硬幣數來找，而不是全部都用1元塞給我們。
動態規劃(Dynamic Programming，簡稱DP)是一種解決問題的技巧，主要被用來優化那些「記不住自己過去曾解出來的答案所以只好重複再解」的演算法，讓它們可以「記憶」已經找出來的答案，從而不斷利用，以大大降低時間複雜度(從指數級降到線性)。
若正整數a除以正整數b可以整除，則稱b為a的因數(Factor)，a為b的倍數(Multiple)，1是所有正整數最小的因數，任意正整數最大的因數就是該正整數本身。若a同時是x和y的因數，則稱a是x和y的公因數(Common Divisor)，如果a是x和y的公因數中最大的一個，則稱a是x和y的最大公因數(Greatest Common Divisor，簡稱GCD)。若a同時是x和y的倍數，則稱a...
我們從小學習算術的時候便知道「四則(加、減、乘、除)運算」的規則，也就是「先乘除、後加減，以及括號先算」。那麼如果我們要撰寫一個可以支援算式輸入且能夠按照四則運算規則求出結果的程式，該怎麼做呢？
費氏搜尋(Fibonacci Search)演算法有點像是二元搜尋(Binary Search)演算法，同樣是在一個已排序好的陣列中搜尋元素，但是它在移動陣列索引值時是去參考費氏數列(Fibonacci Sequence)，而不是像二元搜尋法那樣總是去取索引的中間值。也由於費氏搜尋法在移動陣列索引值時只需要進行加減運算，不需乘、除法，因此它適合被用在不擅長處理乘、除法的CPU上。
圖(graph)是由節點(node)和邊(edge)組合而成的非線性結構，如果我們想要從其中的一個節點開始，走訪到其有直接或是間接連接的其它所有節點，可以依靠深度優先搜尋法(DFS, Depth-first Search)或是廣度優先搜尋法(BFS, Breadth-first Search)來達成。
基數排序(Radix Sort)演算法是可以利用多個鍵值來排序資料的演算法。排序還需要多個鍵值？有時候當然會需要啦！像是要排序檔案時，可以先依照檔案名稱排序後，再依照檔案大小來排，如此一來，整體上來看這些檔案，會是以檔案大小來排序，而相同檔案大小的檔案則是會依照檔案名稱來排序。基數排序法可以將整數的各個位數當作是鍵值，來進行線性時間的排序，比起會依照k(要排序的資料可能的值的數量)愈大而愈吃空間的...
桶排序(Bucket Sort)演算法是先將大量資料分類成少量資料後，再進行排序的演算法。可以透過簡單的運算式來完成資料的分類，在最好的情況之下，資料可以被完全打散，此時的時間複雜度就會是一個線性時間。
這裡所稱的搜尋(Search)，是指在一個已排序好或是尚未排序好的集合中，將指定元素的鍵值(key)或是索引值(index)搜尋出來，或者是給定某個條件，在集合中搜索出符合該條件的資料。在集合內搜尋元素的方法當然不會只有一種，而不同方法搜尋資料的難易度、速度和其它特性自然也會有所不同。搜尋演算法(Search Algorithm)就是搜尋資料的方法，目前已知的方法有很多，在這篇文章中將會整理本站所...