我有一个简单的算法问题:
如果我有一些整数值的元素，比如:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 12 2
，我必须让和为12，需要的最小元素数是1，我就用12
因此，我的问题是你如何:求求和的最小元素数，如果不能输出-1
请建议一个我可以研究的算法，这样我就可以有效地解决这个问题。我已经尝试过使用蛮力，但是对于我的需求来说速度太慢了。
问题是np完全的，可以简化为子集和问题或背包问题。有一种伪多项式时间算法可以用动态规划求解。以下是类似于背包类比的解决方案:-
1. Knapsack capacity = Sum
2. Items have same weight and value
3. Maximize profit
4. if max_profit == Sum then there is a solution
5. else Sum cannot be made from the items given.
6. Evaluate the minimum items needed using matrix alongside the DP.
7. Can also reconstruct all solutions and get the minimum one.
时间复杂度:- O(Sum*Items)
public class SubSetSum {
static int[][] costs;
static int[][] minItems;
public static void calSets(int target,int[] arr) {
costs = new int[arr.length][target+1];
minItems = new int[arr.length][target+1];
for(int j=0;j<=target;j++) {
if(arr[0]<=j) {
costs[0][j] = arr[0];
minItems[0][j] = 1;
}
}
for(int i=1;i<arr.length;i++) {
for(int j=0;j<=target;j++) {
costs[i][j] = costs[i-1][j];
minItems[i][j] = minItems[i-1][j];
if(arr[i]<=j) {
costs[i][j] = Math.max(costs[i][j],costs[i-1][j-arr[i]]+arr[i]);
if(costs[i-1][j]==costs[i-1][j-arr[i]]+arr[i]) {
minItems[i][j] = Math.min(minItems[i][j],minItems[i-1][j-arr[i]]+1);
}
else if(costs[i-1][j]<costs[i-1][j-arr[i]]+arr[i]) {
minItems[i][j] = minItems[i-1][j-arr[i]]+1;
}
}
}
}
// System.out.println(costs[arr.length-1][target]);
if(costs[arr.length-1][target]==target) {
System.out.println("Minimum items need : "+minItems[arr.length-1][target]);
}
else System.out.println("No such Set found");
}
public static void main(String[] args) {
int[] arr = {1,1,1,1, 1 ,1 ,1, 1 ,1, 1 ,1 ,1, 10 ,12, 2};
calSets(12, arr);
}
}
这里有一个递归方法，它应该相当快:
1)如果输入向量的长度为1，如果值等于目标，则返回1，否则返回-1。类似地，如果目标小于输入向量中的任何项，则返回-1。2)否则，循环输入向量中的(唯一)值(出于性能考虑，按降序排列):2a)移除向量的值，并将其从目标中减去。2b)对新向量和新目标递归调用此函数注意:你可以向下传递算法的最大值。step参数，这样如果你已经找到了一个长度为K的解，你就会在这个深度停止递归调用，但不会超过这个深度。记得降低你的最大值。每个递归调用中的步长值。3)收集所有递归调用的值，取最小值(不是-1)并加1返回，或者，如果循环中的所有值都是-1，则返回-1。
免责声明:这是一个漂亮但相对简单的数学广告，它导致非常聪明和快速的计数公式和算法。我知道您可以使用常规编程找到一个更简单有效的解决方案。我只是喜欢这样一个事实:使用适当的计算机代数系统，你可以在一行中完成它:让我们用这个列表得到19:
sage: l = [1,1,1,2,5,2,1,3,12,1,3]; goal = 19
sage: prod((1+t*x^i) for i in l).expand().collect(x).coefficient(x,goal).low_degree(t)
3
25:
sage: goal=25
sage: prod((1+t*x^i) for i in l).expand().collect(x).coefficient(x,goal).low_degree(t)
5
36是不可行的:
sage: goal=36
sage: prod((1+t*x^i) for i in l).expand().collect(x).coefficient(x,goal).low_degree(t)
0
这里有一些细节:只要扩展产品
(1+t*x^l[0]) (1+t*x^l[1]) ... (1+t*x^l[n])
你的列表是l。然后，为求得到S的和所需的最小元素数，收集x^S的系数，返回t中某项的最小次。
在sage中是这样做的:
sage: var("x t")
(x, t)
sage: l = [1,1,1,2,5,2,1,3,12,1,3]
sage: s = prod((1+t*x^i) for i in l)
sage: s = expand(s).collect(x)
sage: print(s)
t^11*x^32 + 5*t^10*x^31 + 2*(t^10 + 5*t^9)*x^30 + 2*(t^10 + 5*t^9 + 5*t^8)*x^29 + (11*t^9 + 20*t^8 + 5*t^7)*x^28 + (t^10 + 4*t^9 + 25*t^8 + 20*t^7 + t^6)*x^27 + 2*(3*t^9 + 10*t^8 + 15*t^7 + 5*t^6)*x^26 + (2*t^9 + 17*t^8 + 40*t^7 + 20*t^6 + 2*t^5)*x^25 + (2*t^9 + 12*t^8 + 30*t^7 + 40*t^6 + 7*t^5)*x^24 + (11*t^8 + 30*t^7 + 35*t^6 + 20*t^5 + t^4)*x^23 + 2*(2*t^8 + 13*t^7 + 20*t^6 + 13*t^5 + 2*t^4)*x^22 + (t^8 + 20*t^7 + 35*t^6 + 30*t^5 + 11*t^4)*x^21 + (t^10 + 7*t^7 + 40*t^6 + 30*t^5 + 12*t^4 + 2*t^3)*x^20 + (5*t^9 + 2*t^7 + 20*t^6 + 40*t^5 + 17*t^4 + 2*t^3)*x^19 + 2*(t^9 + 5*t^8 + 5*t^6 + 15*t^5 + 10*t^4 + 3*t^3)*x^18 + (2*t^9 + 10*t^8 + 10*t^7 + t^6 + 20*t^5 + 25*t^4 + 4*t^3 + t^2)*x^17 + (11*t^8 + 20*t^7 + 5*t^6 + 5*t^5 + 20*t^4 + 11*t^3)*x^16 + (t^9 + 4*t^8 + 25*t^7 + 20*t^6 + t^5 + 10*t^4 + 10*t^3 + 2*t^2)*x^15 + 2*(3*t^8 + 10*t^7 + 15*t^6 + 5*t^5 + 5*t^3 + t^2)*x^14 + (2*t^8 + 17*t^7 + 40*t^6 + 20*t^5 + 2*t^4 + 5*t^2)*x^13 + (2*t^8 + 12*t^7 + 30*t^6 + 40*t^5 + 7*t^4 + t)*x^12 + (11*t^7 + 30*t^6 + 35*t^5 + 20*t^4 + t^3)*x^11 + 2*(2*t^7 + 13*t^6 + 20*t^5 + 13*t^4 + 2*t^3)*x^10 + (t^7 + 20*t^6 + 35*t^5 + 30*t^4 + 11*t^3)*x^9 + (7*t^6 + 40*t^5 + 30*t^4 + 12*t^3 + 2*t^2)*x^8 + (2*t^6 + 20*t^5 + 40*t^4 + 17*t^3 + 2*t^2)*x^7 + 2*(5*t^5 + 15*t^4 + 10*t^3 + 3*t^2)*x^6 + (t^5 + 20*t^4 + 25*t^3 + 4*t^2 + t)*x^5 + (5*t^4 + 20*t^3 + 11*t^2)*x^4 + 2*(5*t^3 + 5*t^2 + t)*x^3 + 2*(5*t^2 + t)*x^2 + 5*t*x + 1
好，这是一个巨大的表达式。这里的一个很好的特征是如果我取x^17的系数我得到:
sage: s.coefficient(x, 17)
2*t^9 + 10*t^8 + 10*t^7 + t^6 + 20*t^5 + 25*t^4 + 4*t^3 + t^2
说的是:术语10*t^7告诉我有10种不同的方法可以用7数得到和17。另一个例子，有25种方法得到17使用4数字(25*t^4)。
也因为这个表达式以t^2结束，我知道我只需要两个数字来得到17。不幸的是，这并没有告诉我们是哪些数字。
如果你想了解这个技巧，看看维基百科关于生成函数的文章和这个页面。
注1:这不是最有效的，因为我计算的比你需要的多得多。这个巨大的表达式实际上描述并以某种方式计算了所有可能的选择(即列表长度的2^)。但它是一行:
sage: prod((1+t*x^i) for i in l).expand().collect(x).coefficient(x,17).low_degree(t)
2
仍然相对有效:
sage: %timeit prod((1+t*x^i) for i in l).expand().collect(x).coefficient(x,17).low_degree(t)
10 loops, best of 3: 42.6 ms per loop
注2:仔细考虑后，我还意识到以下问题:生成级数只是紧凑编码，如果您试图实现动态规划解决方案，您将编写。
我不认为这个解决方案是最佳的，但它很容易理解和使用，你按降序对元素进行排序，然后你取每个元素并尝试将其适合你的数字。如果你有一个数列[5,6,2,7]，你需要把这个数列[7,6,5,2]重新排序，然后取7，然后你需要提取8，所以取6，然后你还需要2，检查5，但它太大了，你会跳过它，检查最后一个数字2，它是完美的，完成了你的数字。所以你会输出3。这是算法的最坏情况是O(n)但在12的例子中，它将是0(1)因为你将从有序序列的第一次检查中选择12。(运行时间只适用于选择项目的程序，不适用于排序程序)
resolve_sum(ordered_items[], number) {
count = 0;
aux = number;
i = 0;
while (aux - ordered_items[i] <= 0) {
count = count + 1;
aux = aux - ordered_items[i];
i = i + 1;
}
if (aux == 0) return count;
else return -1;
}
我没有包括排序算法，你可以选择一个你最熟悉的，或者尝试学习一个新的有效的算法。链接排序算法和它们的运行时间。这只是一个示例代码，你可以在C/c++或Java或其他你需要的代码中使用。我希望这不是太暴力。