Есть ли способ использовать алгоритм рекурсии muilty-вершин - PullRequest
0 голосов
/ 26 марта 2020

У меня есть проблема, подобная этой:

  • Учитывая массив a[n] (с размером n <= 6 и элементами a [i] <= 60), за один раз вы можете уменьшить три (разные, <code>i1 != i2 != i3 != i1) элемента массива: один элемент на 9 a[i1]-=9, один на 3 a[i2]-=3, а оставшийся на 1 a[i3]-=1.
  • Рассчитайте наименьшее время для уменьшения всех элементов массива выше до a[i] <= 0.

Итак, с этой проблемой, я думаю, я буду подсчитывать все возможные способы вычитать рекурсией и вернуть минимальное значение времени, это моя идея (неверно)

package Test;

import java.util.ArrayList;

public class hard {

    static int minCount = Integer.MAX_VALUE;
    static int count = 0;
    static int time = 1;
    static ArrayList<Integer> a = new ArrayList<>();

    static boolean allDie(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            if (a[i]>0)
                return false;
        }
        return true; 
    }

    static void res(int x, int y, int z, int[] a, boolean[] visited) {
        int x1 = x; int x2 = y; int x3 = z;

        for (int i = 0; i < a.length; i++) {
            if (!visited[i]) {
                x1=i;
                visited[i]=true;
                break;
            }
        }
        for (int i = 0; i < a.length; i++) {
            if (!visited[i]) {
                x2=i;
                visited[i]=true;
                break;
            }
        }
        for (int i = 0; i < a.length; i++) {
            if (!visited[i]) {
                x3=i;
                visited[i]=true;
                break;
            }
        }

        System.out.println(x1+" "+x2+" "+x3);
        if (allDie(a)) {
            System.out.println("_"+count);
            minCount=Math.min(minCount,count);
            if (x1>=0) a[x1]+=9;
            if (x2>=0) a[x2]+=3;
            if (x3>=0) a[x3]+=1;
            if (x1>=0) visited[x1]=false;
            if (x2>=0) visited[x2]=false;
            if (x3>=0) visited[x3]=false;
            count--;
            return;
        }
        if (x1>=0) a[x1]-=9;
        if (x2>=0) a[x2]-=3;
        if (x3>=0) a[x3]-=1;
        count++;
        if (x1>=0 && a[x1]>0)
            visited[x1] = false;
        if (x2>=0 && a[x2]>0)
            visited[x2] = false;
        if (x3>=0 && a[x3]>0)
            visited[x3] = false;

        res(x1,x2,x3,a,visited);

        count--;
        if (x1>=0) a[x1]+=9;
        if (x2>=0) a[x2]+=3;
        if (x3>=0) a[x3]+=1;
        if (x1>=0) visited[x1]=false;
        if (x2>=0) visited[x2]=false;
        if (x3>=0) visited[x3]=false;
    }
    static int mutaliskAttack(int[] scvs){
        int n=scvs.length;
        for (int i=0; i<n; i++)
            res(i, i, i, scvs, new boolean[n]);
        return minCount;
    }
    public static void main(String[] args) {
        int[] e= {55, 60, 53};
        System.out.println(mutaliskAttack(e)); // = 13
    }

}

Но, кажется, не рассчитывается полностью, он возвращает 14 вместо 13 (правильный ответ), есть ли потери Кстати, когда я рекурсия использую 3 вершины одновременно, как это?

Если у вас есть лучшая идея вместо использования рекурсии, как я, вы можете помочь мне решить этот вопрос?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...