时间戳

首页 > 解决方案 > 通过从整数列表中添加最少数量的元素来获取整数

algorithm - 通过从整数列表中添加最少数量的元素来获取整数

问题描述

给定一个整数列表，[2, 3]我想获得这些数字加起来的最佳组合8。结果应该是[3, 3, 2]。下面的代码可以正常工作。

    fun getBestCombination(targetSum: Int, numbers: Array<Int>)
            : MutableList<Int>? {
        if (targetSum == 0) return mutableListOf()
        if (targetSum < 0) return null
        var bestCombination: MutableList<Int>? = null
        for (number in numbers) {
            val newTarget = targetSum - number
            val result = getBestCombination(newTarget, numbers)
            result?.let {
                it.add(number)
                if (it.size < bestCombination?.size ?: it.size + 1) {
                    bestCombination = it
                }
            }
        }
        return bestCombination
    }

此代码产生[3, 3, 2]正确的结果。

但是上述代码的时间复杂度是指数级的。当我尝试缓存来自重复递归节点的结果时，它不起作用。下面的代码产生[3, 3, 2, 2, 3]我不知道为什么。

    fun getBestCombinationOptimized(
            targetSum: Int,
            numbers: Array<Int>,
            memory: HashMap<Int, MutableList<Int>?> = hashMapOf()
    ): MutableList<Int>? {
        // Looking in the stored results
        if (memory.containsKey(targetSum)) return memory[targetSum]

        if (targetSum == 0) return mutableListOf()
        if (targetSum < 0) return null
        var bestCombination: MutableList<Int>? = null
        for (number in numbers) {
            val newTarget = targetSum - number
            val result = getBestCombinationOptimized(newTarget, numbers, memory)
            result?.let {
                it.add(number)
                if (it.size < bestCombination?.size ?: it.size + 1) {
                    bestCombination = it
                }
            }
        }

        // Caching the result
        memory[targetSum] = bestCombination

        return bestCombination
    }

标签： algorithmkotlinrecursion

解决方案

您的问题被称为带有重复问题的子集和，它是 NP 完全的。因此，您极不可能找到最坏情况的多项式时间算法。

推荐阅读