हास्केल बस्ता

Question

मैं स्काला में प्रत्येक आइटम में से एक के साथ घिरे नेप्सेक समस्या का जवाब लिखा है, और यह transposing की कोशिश की निम्न परिणाम के साथ Haskell करने के लिए:

knapsack :: [ (Int, Int) ] -> [ (Int, Int) ] -> Int -> [ (Int, Int) ] 
knapsack xs [] _ = xs 
knapsack xs ys max = 
    foldr (maxOf) [ ] [ knapsack (y : xs) (filter (y /=) ys) max | y <- ys 
     , weightOf(y : xs) <= max ] 

maxOf :: [ (Int, Int) ] -> [ (Int, Int) ] -> [ (Int, Int) ] 
maxOf a b = if valueOf a > valueOf b then a else b 

valueOf :: [ (Int, Int) ] -> Int 
valueOf [ ]  = 0 
valueOf (x : xs) = fst x + valueOf xs 

weightOf :: [ (Int, Int) ] -> Int 
weightOf [ ]  = 0 
weightOf (x : xs) = snd x + weightOf xs 

मैं सुझावों के लिए पर नहीं देख रहा हूँ कोड को साफ करने के लिए, बस इसे काम करने के लिए। मेरी जानकारी के लिए यह करना चाहिए निम्नलिखित:

• प्रत्येक टपल विकल्प के लिए (वाईएस में)
  • यदि वर्तमान टपल (y) और चल रहा है कुल (XS) संयुक्त के वजन से कम है क्षमता
  • , इष्टतम नैपसैक कि वर्तमान टपल और वर्तमान कुल (XS) शामिल हैं पाने
• अंत में उपलब्ध tuples (वाईएस में) कम वर्तमान टपल का उपयोग कर, इन परिणामों और वापसी की सबसे अधिक मूल्यवान मिल यह

* संपादित करें: * क्षमा करें, क्या गलत है यह कहना भूल गया ... तो यह ठीक से संकलित करता है, लेकिन यह गलत जवाब देता है। निम्नलिखित आदानों के लिए, मैं क्या उम्मीद और यह क्या पैदा करता है:

knapsack [] [(1,1),(2,2)] 5 
Expect: [(1,1),(2,2)] 
Produces: [(1,1),(2,2)] 

knapsack [] [(1,1),(2,2),(3,3)] 5 
Expect: [(2,2),(3,3)] 
Produces: [] 

knapsack [] [(2,1),(3,2),(4,3),(6,4)] 5 
Expect: [(2,1),(6,4)] 
Produces: [] 

तो मैं सोच रहा था क्या विसंगति के कारण हो सकता है?

समाधान, धन्यवाद sepp2k रहे हैं:

ks = knapsack [] 

knapsack :: [ (Int, Int) ] -> [ (Int, Int) ] -> Int -> [ (Int, Int) ] 
knapsack xs [] _ = xs 
knapsack xs ys max = 
    foldr (maxOf) [ ] (xs : [ knapsack (y : xs) (ys #- y) max 
          | y <- ys, weightOf(y : xs) <= max ]) 

(#-) :: [ (Int, Int) ] -> (Int, Int) -> [ (Int, Int) ] 
[ ]  #- _ = [ ] 
(x : xs) #- y = if x == y then xs else x : (xs #- y) 

maxOf :: [ (Int, Int) ] -> [ (Int, Int) ] -> [ (Int, Int) ] 
maxOf a b = if valueOf a > valueOf b then a else b 

valueOf :: [ (Int, Int) ] -> Int 
valueOf [ ]  = 0 
valueOf (x : xs) = fst x + valueOf xs 

weightOf :: [ (Int, Int) ] -> Int 
weightOf [ ]  = 0 
weightOf (x : xs) = snd x + weightOf xs 

कौन सा अपेक्षित परिणाम देता है, इसके बाद के संस्करण।

Answer 1

आपका पहला मामला आग लगती है जब ys में शामिल होता है। तो knapsack [foo,bar] [] 42 के लिए, आप [foo, bar] पर वापस आएं, जो आप चाहते हैं। हालांकि यह आग नहीं करता है जब ys तत्वों है कि आप अधिकतम वजन से अधिक रखा छोड़कर कुछ भी नहीं होता है, अर्थात knapsack [(x, 20), (y,20)] [(bla, 5)][] लौट सकते हैं और इस प्रकार पिछले परिणाम को छोड़ देगा। ताकि दूसरे मामले केवल आग वहाँ अधिकतम वजन नीचे है कि ys में कम से कम एक तत्व है कि अगर चूंकि यह नहीं है कि तुम क्या आप अपने मामलों का समायोजन करना चाहिए चाहते हैं।

एक तरीका यह है कि ऐसा करने के लिए, आप जिन तत्वों को अधिकतम वजन से अधिक कर दिया जब recursing बाहर निकालने के लिए इतना है कि उस परिदृश्य बस ऐसा नहीं हो सकता होगा।

एक और तरीका मामलों के क्रम को स्विच करना और पहले मामले में एक गार्ड जोड़ना होगा जो कहता है कि ys में कम से कम एक तत्व होना चाहिए जो आपको कुल वजन (और अन्य मामले को समायोजित नहीं करता) खाली होने के लिए ys की आवश्यकता है)।

पुनश्च: अपने कोड के साथ एक और असंबंधित समस्या यह है कि डुप्लिकेट पर ध्यान नहीं देता है। अर्थात। यदि आप सूची [(2,2), (2,2)] पर इसका इस्तेमाल यह कार्य करेगा के रूप में यदि सूची थी सिर्फ [(2,2)] क्योंकि filter (y /=) ys सिर्फ एक नहीं y की सभी घटनाओं बाहर फेंक देंगे।

Answer 2

अपने काम संस्करण पर कुछ सुधार:

import Data.List 
import Data.Function(on) 

ks = knapsack [] 

knapsack :: [(Int, Int)] -> [(Int, Int)] -> Int -> [(Int, Int)] 
knapsack xs [] _ = xs 
knapsack xs ys max = 
    foldr (maxOf) [] (xs: [knapsack (y:xs) (delete y ys) max 
          | y <- ys, weightOf(y:xs) <= max ]) where 
          weightOf = sum . map snd 

maxOf :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)] 
maxOf a b = maximumBy (compare `on` valueOf) [a,b] where 
      valueOf = sum . map fst 

Answer 3

मैं एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर सुझाव दे सकता है?0-1 knapsack समस्याओं को हल करने का यह तरीका लगभग दर्दनाक रूप से धीमा है, कम से कम जब चर की मात्रा लगभग 20 से अधिक हो जाती है। हालांकि यह आसान है, यह बहुत ही अप्रभावी है। यहाँ यह पर मेरे शॉट है:

import Array 

-- creates the dynamic programming table as an array 
dynProgTable (var,cap) = a where 
    a = array ((0,0),(length var,cap)) [ ((i,j), best i j) 
         | i <- [0..length var] , j <- [0..cap] ] where 
     best 0 _ = 0 
     best _ 0 = 0 
     best i j 
      | snd (var !! (i-1)) > j = a!decline 
      | otherwise   = maximum [a!decline,value+a!accept] 
       where decline = (i-1,j) 
         accept = (i-1,j - snd (var !! (i-1))) 
         value = fst (var !! (i-1)) 

--Backtracks the solution from the dynamic programming table 
--Output on the form [Int] where i'th element equals 1 if 
--i'th variable was accepted, 0 otherwise. 
solve (var,cap) = 
    let j = cap 
     i = length var 
     table = dynProgTable (var,cap) 
     step _ 0 _ = [] 
     step a k 0 = step table (k-1) 0 ++ [0] 
     step a k l 
      | a!(k,l) == a!(k-1,l) = step a (k-1) l ++ [0] 
      | otherwise   = step a (k-1) (l - snd (var !! (k-1))) ++ [1] 
    in step table i j 

इनपुट (वर, टोपी) में, वर 2-tuples के रूप में चरों की सूची (ग, डब्ल्यू) है, जहां सी लागत है और w है वजन। टोपी अधिकतम वजन भत्ता है।

मुझे यकीन है कि इसके बाद के संस्करण कोड को साफ किया जा सकता है इसे और अधिक पठनीय और स्पष्ट बनाने के लिए कर रहा हूँ, लेकिन यह है कि कैसे यह मेरे लिए निकला है :) कहाँ Landei से कोड स्निपेट के ऊपर कम है, अपने कंप्यूटर के साथ ही कंप्यूटिंग उदाहरणों उम्र ले लिया 20 चर उपरोक्त गतिशील प्रोग्रामिंग दृष्टिकोण ने मुझे 1000 चर के लिए एक समाधान दिया है।

यदि आपको गतिशील प्रोग्रामिंग के बारे में पता नहीं है, तो आपको यह लिंक देखना चाहिए: Lecture slides on dynamic programming, इससे मुझे बहुत मदद मिली।

सरणी के परिचय के लिए, Array tutorial देखें।