SPOILERS: http://www.spoj.pl/problems/KNAPSACK/ üzerinde çalışıyorum, eğer sizin için olası bir çözümü istemiyorsanız, göz atmayın.Bu hafızaya alınmış DP tablosu SPOJ için ne kadar yavaş?
Ortak metin:
type Item = (Weight, Value)
type Weight = Int
type Value = Int
weight :: Item -> Weight
weight = fst
value :: Item -> Value
value = snd
makeItem :: [String] -> Item
makeItem [w, v] = (read w, read v)
Ve birincil işlevini:
import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)
main = interact knapsackStr
knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
where [capacity, numItems] = map read . words $ head ls
ls = lines str
items = map (makeItem . words) $ take numItems $ tail ls
Bazı türleri ve yardımcıları sahne ayarlamak için
knapsack :: [Item] -> Weight -> Int -> Value
knapsack itemsList = go
where go = memo2 integral integral knapsack'
items = fromList $ (0,0):itemsList
knapsack' 0 _ = 0
knapsack' _ 0 = 0
knapsack' w i | wi > w = exclude
| otherwise = max exclude include
where wi = weight item
vi = value item
item = items `index` i
exclude = go w (i-1)
include = go (w-wi) (i-1) + vi
Ve bu kod çalışır; SPOJ örnek test durumunda takmayı denedim ve doğru sonucu üretir. Ancak bu çözümü SPOJ'a sunduğumda (Luke Palmer'ın MemoCombinator'larını ithal etmek yerine, gerekli parçaları kopyalanan ve gönderilen kaynağa yapıştırıyorum), zaman sınırını aşıyor. =/
Neden olduğunu anlamıyorum; Ben asked earlier 0-1 sırt çantası gerçekleştirmek için verimli bir yol hakkında, ve ben bu kadar hızlı olduğu konusunda oldukça ikna oldum: Sadece üretmek için kesinlikle ihtiyaç duyduğu alt girişleri yinelemeli olarak hesaplayan bir hatırlatılmış işlevi doğru sonuç. Bir şekilde hatıra dağıttım mı? Bu kodda eksik olduğum bir yavaş nokta var mı? SPOJ, Haskell'e karşı önyargılı mı?
Gönderimin en üstüne {-# OPTIONS_GHC -O2 #-} koydum, ancak yardımcı olmadı. 2B dizi Sequence s kullanan benzer bir çözüm denedim, ancak çok yavaş olarak reddedildi.
Profil yapmayı denediniz mi? Genel olarak, bu memoisation'un çoğu görev için büyük bir yardım olduğunu bulamadım. Ayrıca, bir diziyi kullanmak burada çok yardımcı görünmüyor, belki de 'Harita' yerine? – ivanm
Bize tüm kodu sağlanan gerekli notlarla birlikte gösterebilir misiniz? Bu sorunu teşhis etmeyi kolaylaştırır. –
"İndeks" işlemi "O" (log (min (i, n-i))) 'dir (mezara göre). Belki bir Array veya Vector kullanmalısınız. –