如何解决该贪心/动态规划问题？——严格超目标和系数组合求解

Great question! From your examples, it’s clear you’re not just looking for any valid combo—you want the one that uses the fewest total numbers (since in example 2, 0*1 +3*3 +1*5 uses 4 numbers vs. 9*1 +0*3 +1*5 which uses 10). That makes perfect sense, so let’s break down how to find this optimal solution.

Core Insight: Prioritize Larger Numbers #

Larger values get us closer to (and past) the target faster, so we should start with the biggest numbers first. However, pure greedy logic can sometimes fail (like when using the maximum possible of a large number leaves us exactly at the target, not above it). We’ll combine greedy thinking with backtracking to adjust and find the best solution.

Step-by-Step Solution #

1. Preprocess the Input #

• Remove any zeros from the nums array—they don’t contribute to the sum and only add unnecessary coefficients.
• Sort the remaining numbers in descending order so we handle the largest values first, while keeping track of their original indices to map back later.

2. Backtracking with Pruning #

We’ll use a recursive backtracking approach to test different counts of each number, while cutting off paths that can’t possibly beat our current best solution (to save time):

• Start with an initial "best" solution set to a very high number (like target +1, since the worst case is using target+1 1s).
• For each number (starting from largest), try using as many copies as possible first, then work our way down to zero.
  • If using k copies of the current number already makes the sum exceed the target: check if this uses fewer total numbers than our current best, and update if so.
  • If the sum is still below/equal to the target: recurse on the next smaller number, adding k to our total coefficient count.
• Prune any path where the total coefficient count is already equal to or higher than our current best—no need to waste time here.

3. Restore Original Array Order #

Since we sorted the array, we need to map our final coefficients back to the original order of nums to match your example format.

Working Code Example (Python) #

def find_optimal_coefficients(target, nums):
    # Preprocess: remove zeros, keep track of original indices
    original_with_indices = [(num, idx) for idx, num in enumerate(nums) if num > 0]
    if not original_with_indices:
        return None  # No positive numbers can exceed the target
    
    # Sort descending by value, keep original indices
    sorted_nums = sorted(original_with_indices, key=lambda x: (-x[0], x[1]))
    sorted_values = [item[0] for item in sorted_nums]
    sorted_indices = [item[1] for item in sorted_nums]
    n = len(sorted_values)
    
    best_total = float('inf')
    best_sorted_coeffs = None
    
    def backtrack(index, current_coeffs, current_sum, total_coeffs):
        nonlocal best_total, best_sorted_coeffs
        # Prune: skip if we can't beat the current best
        if total_coeffs >= best_total:
            return
        
        # Check if we've exceeded the target
        if current_sum > target:
            if total_coeffs < best_total:
                best_total = total_coeffs
                best_sorted_coeffs = current_coeffs.copy()
            return
        
        # Out of numbers to try
        if index == n:
            return
        
        current_num = sorted_values[index]
        # Max possible copies to try: enough to potentially exceed the target
        max_possible = (target - current_sum) // current_num + 1
        
        # Try from most to least copies to find optimal solutions fast
        for k in range(max_possible, -1, -1):
            current_coeffs.append(k)
            backtrack(
                index + 1,
                current_coeffs,
                current_sum + k * current_num,
                total_coeffs + k
            )
            current_coeffs.pop()
    
    backtrack(0, [], 0, 0)
    
    # Map coefficients back to the original array order
    original_coeffs = [0] * len(nums)
    for idx, coeff in zip(sorted_indices, best_sorted_coeffs):
        original_coeffs[idx] = coeff
    
    return original_coeffs

# Test Example 1
target_1 = 9
nums_1 = [3,5,7]
print(find_optimal_coefficients(target_1, nums_1))  # Output: [1, 0, 1] → 3*1 +7*1=10>9

# Test Example 2
target_2 = 13
nums_2 = [1,3,5]
print(find_optimal_coefficients(target_2, nums_2))  # Output: [0, 3, 1] →3*3 +5*1=14>13

Why This Works #

• Greedy first, adjust as needed: Starting with large numbers quickly finds potential optimal solutions. Backtracking fixes cases where greedy gets stuck (like example 2: 25=10 plus 13=13 isn’t over, so we drop one 5 and add three 3s to hit 14).
• Pruning keeps it efficient: We avoid exploring paths that can’t possibly be better than our current best solution, saving computation time.

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