组合数组元素构建目标值的算法解析

问题描述

给定一个由连续正整数组成的数组N和一个目标整数M，计算使用以下两种方式构建M的方法总数：

仅使用数组N中的元素（每个元素可以重复使用）
使用一个不在N中的元素x（x必须小于N中的最小元素），再加上N中的元素（同样可以重复使用）

示例分析

示例1：


输入：N = [1, 2], M = 4
输出：4
解释：
方法1：1+1+1+1
方法2：1+1+2
方法3：2+2
方法4：使用x=0（如果允许），加上1+1+2（但通常x最小为1）

示例2：


输入：N = [2, 5], M = 4
输出：1
解释：
方法1：2+2=4
（不能使用x=1，因为1+3=4但3不在N中）

算法思路

这个问题可以分解为两个子问题：

完全背包问题：计算仅使用N中元素组成M的方法数
扩展背包问题：计算使用一个额外元素x（x < min(N)）加上N中元素组成M的方法数

动态规划解法

我们使用动态规划来解决这个组合问题：

java
public static int countAssemblyMethods(int[] N, int M) {
    // 情况1：仅使用N中的元素（可重复使用）
    int ways1 = countUnboundedSubsetSum(N, M);
    
    // 情况2：使用一个不在N中的元素x（x < N[0]），再加上N中的元素
    int ways2 = 0;
    if (N.length > 0 && N[0] > 1) {
        for (int x = 1; x < N[0]; x++) {
            if (M > x) {
                ways2 += countUnboundedSubsetSum(N, M - x);
            } else if (M == x) {
                ways2 += 1;  // 单独使用x的情况
            }
        }
    }
    
    return ways1 + ways2;
}

完全背包实现

java
private static int countUnboundedSubsetSum(int[] nums, int sum) {
    int[] dp = new int[sum + 1];
    dp[0] = 1;  // 和为0只有一种方法：不选任何元素
    
    for (int num : nums) {
        for (int i = num; i <= sum; i++) {
            dp[i] += dp[i - num];
        }
    }
    
    return dp[sum];
}

完整代码

java
import java.util.Scanner;

public class ArrayAssembly {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入数组N
        String[] nStr = scanner.nextLine().split(" ");
        int[] N = new int[nStr.length];
        for (int i = 0; i < nStr.length; i++) {
            N[i] = Integer.parseInt(nStr[i]);
        }
        
        // 读取整数M
        int M = Integer.parseInt(scanner.nextLine());
        
        // 计算并输出组装方法数量
        System.out.println(countAssemblyMethods(N, M));
        
        scanner.close();
    }
    
    public static int countAssemblyMethods(int[] N, int M) {
        // 情况1：仅使用N中的元素（可重复使用）
        int ways1 = countUnboundedSubsetSum(N, M);
        
        // 情况2：使用一个不在N中的元素x（x < N[0]），再加上N中的元素（可重复）
        int ways2 = 0;
        if (N.length > 0 && N[0] > 1) {
            for (int x = 1; x < N[0]; x++) {
                if (M > x) {
                    ways2 += countUnboundedSubsetSum(N, M - x);
                } else if (M == x) {
                    ways2 += 1;  // 单独使用x的情况
                }
            }
        }
        
        return ways1 + ways2;
    }
    
    // 允许重复使用元素的子集和计算（完全背包）
    private static int countUnboundedSubsetSum(int[] nums, int sum) {
        int[] dp = new int[sum + 1];
        dp[0] = 1;
        
        for (int num : nums) {
            for (int i = num; i <= sum; i++) {
                dp[i] += dp[i - num];
            }
        }
        
        return dp[sum];
    }
}

复杂度分析

时间复杂度：O(M×n)，其中n是数组N的长度
空间复杂度：O(M)，用于存储DP数组

边界情况处理

空数组N：只能使用x=M（如果允许）
M=0：只有一种方法（不选任何元素）
N中包含1：x的取值会减少（因为x必须小于min(N)）

实际应用

这类组合问题在实际中有广泛应用，例如：

货币找零问题
资源分配问题
密码学中的组合加密
游戏开发中的道具合成系统

总结

通过将问题分解为两个子问题，并运用动态规划技术，我们能够高效地计算出所有可能的组合方式。关键在于：

正确识别问题类型（完全背包问题）
处理好边界条件
将复杂问题分解为更小的子问题

这种解法不仅适用于本问题，其思路也可以推广到其他类似的组合问题中。

思考题：如果题目改为不允许重复使用N中的元素，算法应该如何修改？欢迎在评论区分享你的解决方案！

目录