验证是否可以根据序列 (a,b,c) 的组合生成数字 X

Question

我快要发疯了，想找出一种方法来制作一个不会尝试每一种组合的程序。一个简单的例子：我想知道是否可以通过将系列 (2,5,10,20) 中的数字相加来生成 11，是否有一种简单的方法可以做到这一点而无需尝试每一种可能性？在这种情况下，我们可以用三个 2 和一个 5 来完成。谢谢

Answer 1

我想我想出了某种解决方案

您必须按从高到低的顺序排列清单。它给了我们 [20, 10, 5, 2]
然后，我们将使用某种堆栈。

我们从 n=0 开始

一个。您将列表的第 n 个元素放在堆栈的顶部。

b。如果进入堆栈的数字总和大于目标数字，则删除堆栈的最后一个元素并将 return 指向 a。 n=n+1。如果你从栈中取出的元素是你的小号，那么你也取出下面的元素，return指向a。其中 n=（您集合中最后删除的数字的索引）+1

c。如果不是，你再尝试添加一次，return到b点。

d。这个算法是递归的，当你从你的堆栈中删除最后一个数字时它会停止，这个数字是你的较低数字（那么你不能从你的集合中生成数字），或者当你的堆栈中的数字总和等于你的目标号码（然后你可以从你的集合中生成它）

运行示例：目标 11，设置 [20,10,5,2]

堆栈状态：空，n=0
将 20 放入堆栈：堆栈状态：[20] > 11，从堆栈中移除 20 => n=1
将 10 放入堆栈：堆栈状态：[10] < 11，n=1
将 10 放入堆栈：堆栈状态：[10, 10] > 11，从堆栈中移除 10 => n=2
将 5 放入堆栈：堆栈状态：[10,5] > 11，从堆栈中移除 5 => n=3
将 2 放入堆栈：堆栈状态：[10,2] > 11，从堆栈中删除 2 和 10 => n=2
将 5 放入堆栈：堆栈状态：[5] < 11，n=2
将 5 放入堆栈：堆栈状态：[5,5] < 11，n=2
将 5 放入堆栈：堆栈状态：[5,5,5] > 11，从堆栈中移除 5 => n=3
将 2 放入堆栈：堆栈状态：[5,5,2] > 11，从堆栈中删除 2 和 5 => n=3
将 2 放入堆栈：堆栈状态：[5,2] < 11，n=3
将 2 放入堆栈：堆栈状态：[5,2,2] < 11，n=3
将 2 入栈：栈状态：[5,2,2,2] = 11，你赢了

Answer 2

一种方法是制定一个 LP/IP 模型。这是一个最小化加数总数的优化模型（使用 ojAlgo 编码）。

final Variable tmpVar02 = new Variable("02").weight(1.0).lower(0.0).integer(true);
final Variable tmpVar05 = new Variable("05").weight(1.0).lower(0.0).integer(true);
final Variable tmpVar10 = new Variable("10").weight(1.0).lower(0.0).integer(true);
final Variable tmpVar20 = new Variable("20").weight(1.0).lower(0.0).integer(true);

final ExpressionsBasedModel tmpModel = new ExpressionsBasedModel();
tmpModel.addVariable(tmpVar02);
tmpModel.addVariable(tmpVar05);
tmpModel.addVariable(tmpVar10);
tmpModel.addVariable(tmpVar20);

final Expression tmpRequired = tmpModel.addExpression("Required").level(11.0);
tmpRequired.setLinearFactor(tmpVar02, 2.0);
tmpRequired.setLinearFactor(tmpVar05, 5.0);
tmpRequired.setLinearFactor(tmpVar10, 10.0);
tmpRequired.setLinearFactor(tmpVar20, 20.0);

final Result tmpResult = tmpModel.minimise();

System.out.println(tmpResult);
System.out.println();
System.out.println(tmpModel);

运行代码会产生以下输出：OPTIMAL 4.0 @ [3.0, 1.0, 0.0, 0.0]

验证是否可以根据序列 (a,b,c) 的组合生成数字 X

Verify if a number X can be generated based on a combination of a series (a,b,c)

mathematical-optimization