gpt4 book ai didi

java - 一种操作插入程序的优化算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:17:07 25 4
gpt4 key购买 nike

我目前的程序需要 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");
}
}

是否有更快的方法得出类似的结论?

最佳答案

这个问题可以使用动态规划范式在 O(NK²) 中解决,其中 K 是目标目标的最大可能值。这不是很好,也许有更快的算法,但它仍然比 O(2^N) 蛮力解决方案好很多。

首先让我们定义一个循环来解决这个问题:令 G 为目标值,f(i,j,k) 为返回的函数:

  • 1 如果我们可以仅使用索引 i 及以后的元素达到值 G-j-k
  • 0 否则

我们将使用 j 作为保存当前总和的累加器,将 k 作为保存当前乘法链的总积的累加器,您很快就会明白。

重复的基本情况是:

  • f(N,x,y) = 1 if 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[i]) , f(i+1,j,k*v[i]) )

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[i]) , f(i+1,j,(i==0?v[i]:k *v[i])) )

最后,我们应用记忆化/动态规划范式来优化递归的计算。在算法执行期间,我们将跟踪每个计算的状态,因此当另一个递归调用再次调用该状态时,我们只返回存储的值而不是再次计算其整个递归树。不要忘记这样做,否则由于重新计算子问题,您的解决方案将与蛮力解决方案一样慢(甚至更糟)。如果你需要一些关于 DP 的资源,你可以从这里开始:https://en.wikipedia.org/wiki/Dynamic_programming

关于java - 一种操作插入程序的优化算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39760254/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com