从M个数组各取一个元素，求≤N最大和及最接近N和的算法问询

Question 1: Algorithm to Find Maximum Sum ≤N from Each Array #

To solve this problem efficiently, we’ll use a dynamic programming (DP) approach with pruning—brute-forcing all combinations is infeasible for large M or array sizes, so this method keeps track of only valid, useful sums as we process each array.

Step-by-Step Approach #

1. Initialize DP State:

   • Start with the first array. Collect all elements ≤N (any element larger than N can’t contribute to a valid sum). Store these as our initial set of possible sums.
   • Deduplicate this set (duplicate elements don’t add new possibilities) to save space.

2. Iterate Through Remaining Arrays:
   For each subsequent array:

   • Generate New Sums: For every sum in the current DP set, add each element from the current array. If the new sum is ≤N, add it to a temporary set (using a set automatically handles duplicates).
   • Prune Redundant Sums: Convert the temporary set to a sorted list (descending order). We can’t discard smaller sums entirely (they might combine with future elements to form valid sums when larger sums would exceed N), but deduplicating is essential to keep the set manageable.
   • Update DP Set: Replace the current DP set with the pruned temporary set. If the set becomes empty at any point, no valid sum exists—we can break early.

3. Get the Result:
   After processing all arrays, the largest value in the DP set is your answer. If the set is empty, all possible combinations exceed N.

Question 2: Applying the Algorithm to Your Example #

Let’s assume your input arrays are split into two groups (a logical split given the 16-element sequence):

• Array 1: [13, 2, 17, 5, 2, 3, 4, 5, 6]
• Array 2: [1, 70, 9, 3, 90, 2, 25]
• Limit N = 72

Using our algorithm:

1. Initial DP Set: From Array 1, all elements are ≤72, so initial sums are {2, 3, 4, 5, 6, 13, 17} (deduplicated and sorted).
2. Process Array 2:
   • For each sum in the initial set, add elements from Array 2:
     • 2 + 70 = 72 (exactly equal to N)
     • Other combinations like 17+25=42, 13+25=38, etc., are all ≤72 but smaller than 72.
   • The temporary set will include 72, 42, 38, and other valid sums.
3. Result: The maximum sum ≤72 is 72, achievable by picking 2 from the first array and 70 from the second.

Even if the arrays are split differently (e.g., more than two arrays), the algorithm will still correctly find the closest valid sum by iteratively building up possible sums and pruning irrelevant ones.

Quick Note on Your Input Code #

Your code reads T, B, and N but doesn’t use T and B—you might want to remove those if they’re not needed. Also, add checks for edge cases like empty arrays or all elements exceeding N to make the code more robust.

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