15

我已经在 Haskell 中编写了0-1 背包问题。我对迄今为止所取得的懒惰和普遍性水平感到相当自豪。

我首先提供用于创建和处理惰性二维矩阵的函数。

mkList f = map f [0..]
mkTable f = mkList (\i -> mkList (\j -> f i j))

tableIndex table i j = table !! i !! j

然后我为给定的背包问题制作一个特定的表

knapsackTable = mkTable f
    where f 0 _ = 0
          f _ 0 = 0
          f i j | ws!!i > j = leaveI
                | otherwise = max takeI leaveI
              where takeI  = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i
                    leaveI = tableIndex knapsackTable (i-1) j

-- weight value pairs; item i has weight ws!!i and value vs!!i
ws  = [0,1,2, 5, 6, 7] -- weights
vs  = [0,1,7,11,21,31] -- values

最后用几个辅助函数来查看表格

viewTable table maxI maxJ = take (maxI+1) . map (take (maxJ+1)) $ table
printTable table maxI maxJ = mapM_ print $ viewTable table maxI maxJ

这很容易。但我想更进一步。

我想要一个更好的表数据结构。理想情况下，它应该是

  • 未装箱（不可变） [编辑] 没关系
  • 懒惰的
  • 无界
  • O(1)建设时间
  • O(1)查找给定条目的时间复杂度，
    （更实际地，在最坏的情况O(log n)下，其中 ni*j用于查找第 i 行第 j 列的条目）

如果您能解释您的解决方案为什么/如何满足这些理想，则可以加分。

如果您可以进一步概括knapsackTable，也可以加分，并证明它是有效的。

在改进数据结构时，您应该尝试满足以下目标：

  • 如果我要求最大权重为 10 的解决方案（在我当前的代码中，即indexTable knapsackTable 5 105 意味着包括项目 1-5），则只应执行最少的工作量。理想情况下，这意味着无需O(i*j)将表格的每一行的脊椎强制为必要的列长度。如果您认为 DP 意味着评估整个表格，您可以说这不是“真正的”DP。
  • 如果我要求打印整个表格（类似于printTable knapsackTable 5 10），则每个条目的值应计算一次且仅计算一次。给定单元格的值应取决于其他单元格的值（DP 风格：想法是，永远不要重新计算相同的子问题两次）

想法：

对我陈述的理想做出一些妥协的答案将被赞成（无论如何，由我），只要它们提供信息。妥协最少的答案可能是“接受”的答案。

4

5 回答 5

14

首先，您对未装箱数据结构的标准可能有点误导。未装箱的值必须是严格的，它们与不变性无关。我要提出的解决方案是不可变的、惰性的和盒装的。另外，我不确定您希望构建和查询的方式为 O(1)。我提议的结构是懒惰构建的，但是因为它可能是无限的，所以它的完整构建需要无限的时间。对于任何大小为 k 的特定键，查询结构将花费 O(k) 时间，但当然您正在查找的值可能需要更多时间来计算。

数据结构是懒惰的尝试。我在我的代码中使用了 Conal Elliott 的 MemoTrie 库。为了通用性，它采用函数而不是权重和值的列表。

knapsack :: (Enum a, Num w, Num v, Num a, Ord w, Ord v, HasTrie a, HasTrie w) =>
            (a -> w) -> (a -> v) -> a -> w -> v
knapsack weight value = knapsackMem
  where knapsackMem = memo2 knapsack'
        knapsack' 0 w = 0
        knapsack' i 0 = 0
        knapsack' i w
          | weight i > w = knapsackMem (pred i) w
          | otherwise = max (knapsackMem (pred i) w)
                        (knapsackMem (pred i) (w - weight i)) + value i

基本上，它是作为一个带有惰性脊椎和惰性值的 trie 实现的。它仅受键类型的限制。因为整个事情是惰性的，所以在使用查询强制它之前的构造是 O(1)。每个查询都强制沿着 trie 及其值走一条路径，因此对于有界键大小O(log n)，它是 O(1)。正如我已经说过的，它是不可变的，但不是未装箱的。

它将共享递归调用中的所有工作。它实际上不允许您直接打印 trie，但这样的事情不应该做任何多余的工作：

mapM_ (print . uncurry (knapsack ws vs)) $ range ((0,0), (i,w))
于 2011-03-07T22:20:40.920 回答
9

未装箱意味着严格和有界。任何 100% Unboxed 的东西都不能是 Lazy 或 Unbounded。通常的妥协体现在将 [Word8] 转换为 Data.ByteString.Lazy ，其中有未装箱的块（严格的 ByteString），它们以无限制的方式懒惰地链接在一起。

可以使用“scanl”、“zipWith”和我的“takeOnto”制作更高效的表格生成器（增强以跟踪单个项目）。这有效地避免了在创建表时使用 (!!)：

import Data.List(sort,genericTake)

type Table = [ [ Entry ] ]

data Entry = Entry { bestValue :: !Integer, pieces :: [[WV]] }
  deriving (Read,Show)

data WV = WV { weight, value :: !Integer }
  deriving (Read,Show,Eq,Ord)

instance Eq Entry where
  (==) a b = (==) (bestValue a) (bestValue b)

instance Ord Entry where
  compare a b = compare (bestValue a) (bestValue b)

solutions :: Entry -> Int
solutions = length . filter (not . null) . pieces

addItem :: Entry -> WV -> Entry
addItem e wv = Entry { bestValue = bestValue e + value wv, pieces = map (wv:) (pieces e) }

-- Utility function for improve
takeOnto :: ([a] -> [a]) -> Integer -> [a] -> [a]
takeOnto endF = go where
  go n rest | n <=0 = endF rest
            | otherwise = case rest of
                            (x:xs) -> x : go (pred n) xs
                            [] -> error "takeOnto: unexpected []"

improve oldList wv@(WV {weight=wi,value = vi}) = newList where
  newList | vi <=0 = oldList
          | otherwise = takeOnto (zipWith maxAB oldList) wi oldList
  -- Dual traversal of index (w-wi) and index w makes this a zipWith
  maxAB e2 e1 = let e2v = addItem e2 wv
                in case compare e1 e2v of
                     LT -> e2v
                     EQ -> Entry { bestValue = bestValue e1
                                 , pieces = pieces e1 ++ pieces e2v }
                     GT -> e1

-- Note that the returned table is finite
-- The dependence on only the previous row makes this a "scanl" operation
makeTable :: [Int] -> [Int] -> Table
makeTable ws vs =
  let wvs = zipWith WV (map toInteger ws) (map toInteger vs)
      nil = repeat (Entry { bestValue = 0, pieces = [[]] })
      totW = sum (map weight wvs)
  in map (genericTake (succ totW)) $ scanl improve nil wvs

-- Create specific table, note that weights (1+7) equal weight 8
ws, vs :: [Int]
ws  = [2,3, 5, 5, 6, 7] -- weights
vs  = [1,7,8,11,21,31] -- values

t = makeTable ws vs

-- Investigate table

seeTable = mapM_ seeBestValue t
  where seeBestValue row = mapM_ (\v -> putStr (' ':(show (bestValue v)))) row >> putChar '\n'

ways = mapM_ seeWays t
  where seeWays row = mapM_ (\v -> putStr (' ':(show (solutions v)))) row >> putChar '\n'

-- This has two ways of satisfying a bestValue of 8 for 3 items up to total weight 5
interesting = print (t !! 3 !! 5)
于 2011-03-07T18:25:53.590 回答
4

惰性可存储向量： http ://hackage.haskell.org/package/storablevector

无界、惰性、O(chunksize) 构建时间、O(n/chunksize) 索引，其中对于任何给定目的，chunksize 可以足够大。基本上是一个惰性列表，具有一些重要的常数因子优势。

于 2011-03-07T20:14:32.830 回答
4

为了记忆函数，我推荐一个像 Luke Palmer's memo combinators这样的库。该库使用尝试，它是无界的并且具有 O(key size) 查找。（一般来说，你不能做得比 O(key size) 查找更好，因为你总是必须触摸密钥的每一位。）

knapsack :: (Int,Int) -> Solution
knapsack = memo f
    where
    memo    = pair integral integral
    f (i,j) = ... knapsack (i-b,j) ...


在内部，integral组合器可能构建了一个无限的数据结构

data IntTrie a = Branch IntTrie a IntTrie

integral f = \n -> lookup n table
     where
     table = Branch (\n -> f (2*n)) (f 0) (\n -> f (2*n+1))

查找工作如下：

lookup 0 (Branch l a r) = a
lookup n (Branch l a r) = if even n then lookup n2 l else lookup n2 r
     where n2 = n `div` 2

还有其他方法可以构建无限尝试，但这种方法很流行。

于 2011-03-08T08:32:16.757 回答
2

为什么不使用 Data.Map 将另一个 Data.Map 放入其中？据我所知，它相当快。不过也不会偷懒。

不仅如此，您还可以为您的数据实现 Ord 类型类

data Index = Index Int Int

并直接放一个二维索引作为key。您可以通过将此地图生成为列表来实现懒惰，然后只需使用

fromList [(Index 0 0, value11), (Index 0 1, value12), ...]
于 2011-03-07T18:23:29.957 回答