我的程序目前接受N个数字，然后是一个目标。它在数字之间插入"+"或"*"来尝试达到目标。如果它能达到目标，它将打印出正确的操作。然而，它找到答案的方式是通过蛮力，这对于N个数字的大集合是不够的。我当前的代码如下:
public class Arithmetic4{
private static ArrayList<String> input = new ArrayList<String>();
private static ArrayList<String> second_line = new ArrayList<String>();
private static ArrayList<Integer> numbers = new ArrayList<Integer>();
private static ArrayList<String> operations = new ArrayList<String>();
private static ArrayList<Integer> temp_array = new ArrayList<Integer>();
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
readInput(sc);
}
}
public static void readInput(Scanner sc){
String line = sc.nextLine();
input.add(line);
line = sc.nextLine();
second_line.add(line);
dealInput();
}
public static void dealInput(){
String numberS = input.get(0);
String[] stringNumbers = numberS.split("\s+");
for(int i = 0; i < stringNumbers.length; i++){
String numberAsString = stringNumbers[i];
numbers.add(Integer.parseInt(numberAsString));
}
String orderString = second_line.get(0);
String[] stringWhatWay = orderString.split("\s+");
int target = Integer.parseInt(stringWhatWay[0]);
char whatway = stringWhatWay[1].charAt(0);
long startTime = System.currentTimeMillis();
whatEquation(numbers, target, whatway);
long elapsedTime = System.currentTimeMillis() - startTime;
long elapsedMSeconds = elapsedTime / 1;
System.out.println(elapsedMSeconds);
numbers.clear();
input.clear();
second_line.clear();
}
public static void whatEquation(ArrayList<Integer> numbers, int target, char whatway){
if(whatway != 'L' && whatway != 'N'){
System.out.println("Not an option");
}
if(whatway == 'N'){
ArrayList<Integer> tempo_array = new ArrayList<Integer>(numbers);
int count = 0;
for (int y: numbers) {
count++;
}
count--;
int q = count;
calculateN(numbers, target, tempo_array, q);
}
if (whatway == 'L'){
if(numbers.size() == 1){
System.out.println("L " + numbers.get(0));
}
ArrayList<Integer> temp_array = new ArrayList<Integer>(numbers);
calculateL(numbers, target, temp_array);
}
}
public static void calculateN(ArrayList<Integer> numbers, int target, ArrayList<Integer> tempo_numbers, int q){
int sum = 0;
int value_inc = 0;
int value_add;
boolean firstRun = true;
ArrayList<Character> ops = new ArrayList<Character>();
ops.add('+');
ops.add('*');
for(int i = 0; i < Math.pow(2, q); i++){
String bin = Integer.toBinaryString(i);
while(bin.length() < q)
bin = "0" + bin;
char[] chars = bin.toCharArray();
List<Character> oList = new ArrayList<Character> ();
for(char c: chars){
oList.add(c);
}
ArrayList<Character> op_array = new ArrayList<Character>();
ArrayList<Character> temp_op_array = new ArrayList<Character>();
for (int j = 0; j < oList.size(); j++) {
if (oList.get(j) == '0') {
op_array.add(j, ops.get(0));
temp_op_array.add(j, ops.get(0));
} else if (oList.get(j) == '1') {
op_array.add(j, ops.get(1));
temp_op_array.add(j, ops.get(1));
}
}
sum = 0;
for(int p = 0; p < op_array.size(); p++){
if(op_array.get(p) == '*'){
int multiSum = numbers.get(p) * numbers.get(p+1);
numbers.remove(p);
numbers.remove(p);
numbers.add(p, multiSum);
op_array.remove(p);
p -= 1;
}
}
for(Integer n: numbers){
sum += n;
}
if(sum != target){
numbers.clear();
for (int t = 0; t < tempo_numbers.size(); t++) {
numbers.add(t, tempo_numbers.get(t));
}
}
if (sum == target){
int count_print_symbol = 0;
System.out.print("N ");
for(int g = 0; g < tempo_numbers.size(); g++){
System.out.print(tempo_numbers.get(g) + " ");
if(count_print_symbol == q){
break;
}
System.out.print(temp_op_array.get(count_print_symbol) + " ");
count_print_symbol++;
}
System.out.print("n");
return;
}
}
System.out.println("N is Impossible");
}
public static void calculateL(ArrayList<Integer> numbers, int target, ArrayList<Integer> temp_array){
int op_count = 0;
int sum = 0;
int n = (numbers.size() -1);
boolean firstRun = true;
for (int i = 0; i < Math.pow(2, n); i++) {
String bin = Integer.toBinaryString(i);
while (bin.length() < n)
bin = "0" + bin;
char[] chars = bin.toCharArray();
char[] charArray = new char[n];
for (int j = 0; j < chars.length; j++) {
charArray[j] = chars[j] == '0' ? '+' : '*';
}
//System.out.println(charArray);
for(char c : charArray){
op_count++;
if(firstRun == true){
sum = numbers.get(0);
numbers.remove(0);
// System.out.println(sum);
}
if (!numbers.isEmpty()){
if (c == '+') {
sum += numbers.get(0);
} else if (c == '*') {
sum *= numbers.get(0);
}
numbers.remove(0);
}
firstRun = false;
//System.out.println(sum);
if(sum == target && op_count == n){
int count_print_op = 0;
System.out.print("L ");
for(int r = 0; r < temp_array.size(); r++){
System.out.print(temp_array.get(r) + " ");
if(count_print_op == n){
break;
}
System.out.print(charArray[count_print_op] + " ");
count_print_op++;
}
System.out.print("n");
return;
}
if(op_count == n && sum != target){
firstRun = true;
sum = 0;
op_count = 0;
for(int e = 0; e < temp_array.size(); e++){
numbers.add(e, temp_array.get(e));
}
}
}
}
System.out.println("L is impossible");
}
}
是否有更快的方法来得出类似的结论?
这个问题可以使用动态规划范式在0 (NK²)中解决，其中K是目标目标的最大可能值。这不是很好，也许有一个更快的算法，但它仍然比O(2^N)蛮力解决方案好得多。
首先让我们定义一个递归式来解决这个问题:设G为目标值，f(i,j,k)为一个函数，返回:
- 1，如果只使用索引i及以后的元素可以达到G-j-k值 否则
- 0
我们将使用j作为保存当前总和的累加器，使用k作为保存当前乘法链的总乘积的累加器，你很快就会明白的。
递归式的基本情况是:
- f(N,x,y) = 1如果x+y = G(我们已经使用了每个元素并达到了我们的目标)
- f(N,x,y) = 0否则
- f(i,x,y) = 0 i != N and x+y>= G(我们在使用每个元素之前已经超过了目标)
对于其他i值，我们可以将递归定义为:
- f (i, j, k) = max (f (i + 1 j + k v[我]),f (i + 1 j k * v[我]))
max()中的第一个函数调用意味着我们将在当前索引前面加一个"+"号，所以我们当前的乘法链被打破了，我们必须将其总积加到当前的和上，所以第二个参数是j+k，因为我们现在开始一个新的乘法链，它的总积正好是v[i]。
max()内部的第二个函数调用意味着我们将在当前索引之前放一个"*"号，所以我们当前的乘法链仍然在继续，所以第二个参数仍然是j，第三个参数将变成k * v[i]。
我们想要的是f(0,0,0)的值(我们没有使用任何元素，我们当前的累加和等于0)，f(0,0,0)等于1当且仅当问题有解，所以问题解决了。现在让我们回到递归式并修正一个细节:当我们运行f(0,0,0)时，无论v[i]的值是多少，k*v[i]的值都将是0，所以我们必须在计算i = 0的答案时添加一个特殊的检查，最终的递归式看起来像这样:
- f (i, j, k) = max (f (i + 1 j + k v[我]),f (i + 1 j(我= = 0 ? v[我]:k * v[我])))
最后，我们应用记忆/动态规划范式来优化递归式的计算。在算法执行期间，我们将跟踪每个计算的状态，因此当该状态被另一个递归调用再次调用时，我们只需返回存储的值，而不是再次计算其整个递归树。不要忘记这样做，否则由于子问题的重新计算，您的解决方案将与暴力解决方案一样慢(甚至更糟)。如果需要DP上的一些资源，可以从这里开始:https://en.wikipedia.org/wiki/Dynamic_programming