Analysis Of Algorithm'de Takıldığım Soru
-
Hocalar iyi akşamlar. Cuma günü finalim var algoritma dersinden ve bir soruda takıldım , yardımcı olacağınızı ümid ediyorum :)
Soru :
Given the following Coin-Row problem : 3 9 6 3 4 7 6 2 8 1 9
It is required to pick up a subset of items with max amount of values so that no two items ajdacent in the row can be picked up. Solve the problem by using Dynamic Programming method.Soru hakkında en ufak bir fikrim bile yok ve bende şuanda Exhaustive Method konusuna çalışıyorum. Yardımcı olursanız sevinirim :) // Konu bitti şuanda sadece bu konuya odaklandım.
GodKlaus tarafından 30/May/17 23:43 tarihinde düzenlenmiştir
// Knapsack diye bir method çıktı karşıma araştırma yaparken ama insanların çözdüğü soru kalıpları ile bu uyuşmamakta.
// İnsanların çözdüklerinde "Weight ve Value" değerleri var lakin bunda hiçbirisi yok. Kafam karışık şuanda ): -
1 kez up olsun :D Neden kimse çıkmıyor ki koca forumdan -.-
-
Cuma sınav var ve dinamik programlamayı bilmiyorsan büte hazırlanmaya başla derim.
Coin-Row genel bir program. Üzerinden 1 yıldan fazla geçti hatırlamıyorum çözümünü nette kesin vardır ama ona eminim.
-
zeybekustasi bunu yazdı
Cuma sınav var ve dinamik programlamayı bilmiyorsan büte hazırlanmaya başla derim.
Coin-Row genel bir program. Üzerinden 1 yıldan fazla geçti hatırlamıyorum çözümünü nette kesin vardır ama ona eminim.
hocamız kalp krizi geçirdi 1 aydan fazla gelemedi okula. Şuanda konulardan geriyiz ve bize daha önce attığı slaytlardan buldum bu soruyu. İnternette araştırdım senin dediğin konunun benzeri olarak "Knapsack Problem" diye çıktı ama videolarda insanların çözdüğü soru tipi ile buradaki soru tipini bağdaştıramadım :(
-
edit. tekrar okuyunca knapsack de olabilir.. ama ben coin-row olayını anlamadım yani.
araştırınca coin-row türünde sorular olduğunu gördüm. daha önceden bilmiyordum. şuna benziyor:
https://www.youtube.com/watch?v=mSyiRGSAq7k
-
dp problemlerini incele biraz. Memoization kavramını anlaman lazım. dp formula geliştirmenin mantığını anlamadan (yani recursively) hiç bir algoritmayı zaten soruya uygulayamazsın. Bu arada exhaustive methodtan kastın brute force ise hiç bakma :D Algoritma dersinde amaç zaten brute forceden kurtulmak.
Ben geçen dönem aldım algoritmayı, soruların alayı greedy, dp idi. Bu soruya gelecek olursak. Tek boyutlu bir array yeterli olacak. Yan yana iki sayıyı alamadığımızdan birinciden başlayarak 1.index+3.index seçimini sadece 2.indexteki sayıyla karşılastırıp büyük olanı alacaksın ve 3.indexe yazacaksın arrayde. Bu demek oluyor ki ilk 3 indexten max o sayı kadar değer toplayabilirsin. Bunu iterative olarak sona kadar götürürsen, son eleman toplayabileceğin maks değer olur.