3

この問題に対するメモ化とボトムアップアプローチアルゴリズムの処理に問題があります:

、for allのxiような要素の配列があるとします。T 要素の最大合計、T < N を見つけて、それらが異なるサブ配列に配置されるようにしてください。各サブ配列の最初の要素を合計するのではなく、サブ配列の数 K を次のように返す必要があります。良い。-10000 < xi < 100000 < i < N

例で説明する必要があります：

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、配列 = 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 に答える