3

我在处理这个问题的记忆和自下而上的方法算法时遇到了麻烦：

假设您有一个元素数组，xi例如-10000 < xi < 10000,for all 0 < i < N。尝试找到 T 个元素的最大和，T < N 使得它们排列在不同的子数组中。我们不对每个子数组中的第一个元素求和，我们必须返回子数组的数量 K 为出色地。

一个例子应该解释：

T=4, array = 3 9 1 1 7 => (3 9) and (1 7) have maximum sum 16= 9 + 7 ,K = 2

T=4, array = 3 9 6 3 7 => (3 9 6 3) have maximum sum 18 = 9 + 6 + 3 , K = 1

*T = 9, array = 14 11 18 1 1 16 12 18 0 0 11 18 9 5 14 => 连续子数组是 (14 11 18) (1 16 12 18) (11 18) K=3 和 max_sum =11 + 18 + 16 + 12 + 18 + 18 = 93 ** **对于 T=15 数组 = 6 19 -29 15 9 -4 5 27 3 12 -10 5 -2 27 10 -2 11 23 -4 5 => 连续子数组是 (6 19) (-29 15 9) (5 27 3 12) (-2 27 10) (-2 11 23)，其中 K =5 和 max_sum= 19 + 15 + 9 + 27 + 3 + 12 +27 + 10 + 11 + 23=156

这是我到目前为止所做的：

let f[i][j][0] denotes the maximal sum for the first i slots and using j slots, and the i-th slot is not used.

let f[i][j][1] denotes the maximal gain for the first i slots and using j slots , and the i-th slot is used.

显然，f[i][j][k]可以确定f[i+1][j][k]或f[i+1][j+1][k]

细节：

    f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0],f[i][j][1]+G[i+1]);
    f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0],f[i][j][1]);
4

1 回答 1

0

这是 Haskell 中的一个版本。'partitions' 函数由 Daniel Fischer 编写，它以所有可能的方式对列表（或数组）进行分区。其余代码测试长度大于 1 的元素的分区，其组合长度与 T 匹配，并返回总和最大的分区（按要求求和，没有第一个数字）。

import Data.List (maximumBy)
import Data.Ord (comparing)

partitions [] = [[]]
partitions (x:xs) = [[x]:p | p <- partitions xs]
                 ++ [(x:ys):yss | (ys:yss) <- partitions xs]

findMax t xs = 
  let toTest = filter (\z -> (sum $ map length z) == t) 
               $ map (\x -> filter (\y -> length y > 1) x) 
               $ partitions xs
      result = maximumBy (comparing snd) 
               (zip toTest (map (\x -> sum $ map (sum . drop 1) x) toTest))
  in putStrLn( 
       show result 
       ++ " K = " 
       ++ show (length $ fst result))


OUTPUT:
*Main> findMax 4 [3,9,1,1,7]
([[3,9],[1,7]],16) K = 2

*Main> findMax 4 [3,9,6,3,7]
([[3,9,6,3]],18) K = 1

*Main> findMax 9 [14,11,18,1,1,16,12,18,0,0,11,18,9,5,14]
([[14,11,18],[1,16,12,18],[11,18]],93) K = 3
于 2013-03-18T02:23:19.807 回答