所以这是问题所在:
鉴于input = [100 80 66 25 4 2 1],我需要找到最好的组合给我50.
看看这个,最好的是25 + 25 = 50,所以我需要数组中的2个元素.
其他组合包括25+4+4+4+4+4+4+1和25+4+4+4+4+4+2+2+1...等
我需要找到所有可能性,这些可能性为我提供了我想要的价值.
编辑:以及最好的可能性(一个条款数量最少)
这是我到目前为止所做的:首先构建一个新的数组(简单的for循环遍历所有元素并存储在一个新的temp数组中),检查高于我的数组的所有元素(所以对于输入50,元素100, 80,66更高,所以丢弃它们然后我的新阵列是[25 4 2 1]).然后,由此,我需要检查组合.
我做的第一件事是一个简单的if语句检查是否有任何数组元素与我想要的数字完全匹配.所以,如果我想要50,我会检查阵列中是否有50,如果没有,我需要找到组合.
我的问题是,我不完全确定如何找到每一个组合.我一直在努力尝试提出一段时间的算法,但我总是最终陷入困境.
任何帮助/提示将不胜感激.
PS - 我们可以假设数组总是按照从LARGEST到SMALLEST值的顺序排序.
这是动态编程要解决的问题.
创建一个索引为1到50的数组.将每个条目设置为-1.对于输入数组中的每个元素,将数组中的元素设置为0.然后,对于n = 2到50的每个整数,找到所有可能的求和方式.所需的总和数是两个加数的最小值加1.最后,获取索引为50的元素.
您需要解决每个子问题并存储解决方案。例如：
1只能是1。2可以是2或1+1。4可以是4或2+2或2+1+1或1+1+1+1。所以你取出每个子解并存储它，所以当你看到 25=4+4+4+4+4+4+1 时，你已经知道每个 4 也可以表示为 3 种组合之一。
然后，您必须对数字进行排序并检查以避免重复的模式，例如 (2+2)+(2+2)+(2+2)+(1+1+1+1)+(1+1 +1+1)+(1+1+1+1) == (2+1+1)+(2+1+1)+(2+1+1)+(2+1+1)+( 2+1+1)+(2+1+1)。两种情况都有 6 个 2 和 12 个 1。
那有意义吗？