寻求Haskell中满足最大值约束的最优序列填充函数实现

Hey there! Let's break down how to fix your problem and build a function that finds the optimal sequence whose sum doesn't exceed your maximum value.

First, let's look at why your current fill function falls short:

Your fill function uses a greedy, order-dependent approach—it just takes elements in sequence until it can't fit the next one. This works for trivial cases, but it misses truly optimal subsets. For example, if your max is 10 and your list is [6,5,5], your function would take 6 and leave 4 (total sum 6), but the best possible subset is [5,5] with sum 10 and 0 remaining space.

You're absolutely right that pre-sorting and filtering the list simplifies things. First, we can filter out any elements larger than the max (they can never be part of a valid subset), and sorting can help with both readability and potential optimizations later.

This problem is a classic variant of the 0-1 Knapsack Problem—we need to choose a subset of elements where their sum is as large as possible without exceeding the max value. The core idea is to consider two choices for each element: include it in the subset, or skip it. We then pick whichever choice leads to the better (higher sum, lower remaining space) result.

Recursive Approach (For Small Lists) #

Let's start with a clear recursive solution that returns both the remaining space and the optimal subset. This is easy to understand but isn't efficient for very long lists:

-- Returns (remaining space, optimal subset)
bestSubset :: Int -> [Int] -> (Int, [Int])
bestSubset maxVal [] = (maxVal, [])
bestSubset maxVal (x:xs)
  | x > maxVal = bestSubset maxVal xs  -- Skip elements too big to fit
  | otherwise =
      -- Option 1: Include x, then solve for the remaining space
      let (remainingWith, subsetWith) = bestSubset (maxVal - x) xs
      -- Option 2: Skip x, solve for the original max
          (remainingWithout, subsetWithout) = bestSubset maxVal xs
      -- Choose the option with smaller remaining space (i.e., larger sum)
      in if remainingWith < remainingWithout
         then (remainingWith, x : subsetWith)
         else (remainingWithout, subsetWithout)

You can use this like so:

-- Example: max 10, list [6,5,5]
bestSubset 10 [6,5,5]  -- Returns (0, [5,5])

Optimized Dynamic Programming Approach (For Longer Lists) #

The recursive approach has exponential time complexity (O(2^n)), which gets slow quickly for large lists. A dynamic programming (DP) approach is better here—it builds up solutions incrementally and avoids redundant calculations:

import Data.List (sortOn)
import Data.Maybe (fromJust)

bestSubsetDP :: Int -> [Int] -> [Int]
bestSubsetDP maxVal xs =
  let -- Preprocess: filter out elements too big, sort descending (helps with backtracking)
      validElements = filter (<= maxVal) xs
      sortedElements = sortOn negate validElements

      -- DP array: dp !! s is True if sum s is achievable
      dp = foldl updateDP (replicate (maxVal + 1) False) sortedElements
      updateDP currentDP x =
          let -- For each possible sum, check if we can reach it by adding x to an existing sum
              newReachable = map (\s -> s >= x && currentDP !! (s - x)) [0..maxVal]
          in zipWith (||) currentDP newReachable  -- Merge with existing reachable sums

      -- Find the largest achievable sum <= maxVal
      maxAchievableSum = last [s | s <- [0..maxVal], dp !! s]

      -- Backtrack to find which elements make up this sum
      backtrack _ [] = []
      backtrack remainingSum (y:ys)
          | remainingSum >= y && dp !! (remainingSum - y) = y : backtrack (remainingSum - y) ys
          | otherwise = backtrack remainingSum ys
  in backtrack maxAchievableSum sortedElements

Key Notes #

• Preprocessing: Filtering out elements larger than maxVal right away saves unnecessary computation. Sorting (we used descending order here) makes backtracking easier, but you can adjust the sort order if you want subsets in a different order.
• Optimal Definition: The examples above prioritize subsets with the largest sum. If you have ties (multiple subsets with the same max sum), you can modify the comparison logic—for example, to prefer subsets with more elements, or subsets that preserve the original order of elements.
• Performance: The DP approach runs in O(n * maxVal) time, which is much better than the recursive approach for large lists.

内容的提问来源于stack exchange，提问作者Madderote