मैं स्काला में प्रत्येक आइटम में से एक के साथ घिरे नेप्सेक समस्या का जवाब लिखा है, और यह 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
कौन सा अपेक्षित परिणाम देता है, इसके बाद के संस्करण।
समस्या क्या है? क्या यह संकलित नहीं है? क्या यह गलत परिणाम देता है? विशिष्ट होना। – hammar