Перебор вариантов ( Рекурсия, “Рюкзак” )

450
13 августа 2021, 07:30

Я извиняюсь за свои макароны. Дан вес 26 инструментов ( float[] Kaal ), нужно проверить дает ли какой то набор инструментов ( Не больше 13 ) вес равный ТОЧНО 10 кг.

Это все, что есть на данный момент.

import java.util.ArrayList;
import java.util.Random;
public class Kodu2 {
    public static void main(String[] args){
        ArrayList<Float> Uus = new ArrayList <Float>();
        int sum = 0;
        float[] Kaal = new float[26]; 
        for (int i = 0; i < Kaal.length ; i++) {
            Kaal[i] = (float) (Math.random() * 20);
        }
        System.out.println(Kaal);
        System.out.println(Kogum(Kaal, sum, Uus)); 
    }
    public static float Kogum(float[] Kaal, int sum, ArrayList <Float> Uus){
        float n = Kaal.length;
        for (int i = 0; i < 13 ; i++) { 
            float RandomNumber = new Random().nextInt(Kaal.length); 
            if(RandomNumber >= 10){ 
                Kogum(Kaal, sum, Uus); 
            } else {
                Uus.add(RandomNumber); 
            }
            for(Float values : Uus){
                sum += values;
            }
            if(sum == 10){
                System.out.println("Found 10 kg items" + Uus);
            } else {
                Kogum(Kaal,sum, Uus);
            }
        }
        return sum;
    }
}

1) Выдает пока ошибку

2) Тип "Веса" я скорее всего не правильно использую (float)

3) Нужно наверное сразу сумму проверять, вместе с добавлением "RandomNumber"

Очень корява рассказал, но надеюсь понятно. (Если что поправлю)

Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.util.Random.nextInt(Random.java:390)
    at Kodu2.Kogum(Kodu2.java:20)
    at Kodu2.Kogum(Kodu2.java:22)
    at Kodu2.Kogum(Kodu2.java:22)
    at Kodu2.Kogum(Kodu2.java:32)
    at Kodu2.Kogum(Kodu2.java:32)
    at Kodu2.Kogum(Kodu2.java:32)
    at Kodu2.Kogum(Kodu2.java:22)
    .........
Answer 1

Вы взяли почти правильное решение, но не верно подошли к реализации. По пунктам

  • Во время подбора никогда нельзя использовать рандом, вы рискуете а) никогда не получить правильную комбинацию, когда она есть, и б) никогда не получить условий выхода из цикла/рексурсии/бренности бытия. У вас ошибка StackOverflowError - вы попали в бесконечную рекурсию и создали столько экземпляров функции Kogum, что просто забили стэк и новая создаться не смогла. Придумывать какой элемент добавить следующим не нужно, нужно перебрать их все по очереди
  • Что же такое RandomNumber? я сначала решил, что вы складываете в Uus порядковые номера весов, входящих в проверяемый набор. Но в sum вы складываете как раз сумму чисел в Uus, а в нем лежат придуманные в строке float RandomNumber = new Random().nextInt(Kaal.length); числа, что делает бессмысленным содержимое массива Kaal
  • Если все таки RandomNumber - номер элемента из Kaal, просто неправильно ищите сумму в коде из вопроса, то он должен быть int, а не float
  • цикл for нужно заменить условием if(Uus.length>13) return; Цикл тут категорически не нужен, либо решаем задачу циклом, либо рекурсией. Внутри рекурсии может использоваться цикл но не так, как у вас

Блин, хотел по человечески расписать что не так, но слишком много очень глубинных ошибок Вам бы начать с задач попроще или сыскать живого ментора, с которым такие вещи разбирать. Если задача не учебная а практическая - скажите, добавлю к ответу подправленный код. Если учебная - попробуйте что-то попроще и потом уже возвращайтесь к этой задаче

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class Main {
    private static float REQUIRED_WEIGHT = 10f; //вес, который хотим получить
    private static int MAX_EQUIP_COUNT = 13; //максимальное число инструментов в наборе
    private static int TOTAL_EQUIP_COUNT = 26;//общее чсило инструментов
    private static float epsilon = 0.0001f;//точность. Когда работаешь с float или double без нее никак. если задашь одной переменной значение 0.0001f, а другой 1/10000f, они могут быть не равны из-за особенностей float 
    public static void main(String[] args) {
        //Создаем массив весов инструментов 
        float[] weights = new float[TOTAL_EQUIP_COUNT];
        Random random = new Random();
        for (int i = 0; i < weights.length; i++) {
            weights[i] = random.nextInt(20000) / 1000f; //берем случайный int от 0 до 19999 и делим на float 10000, получаем float от 0.0 до 19.999
        }
        System.out.println(Arrays.toString(weights)); //выводим массив весов
        //создаем список, в который будем складывать индексы весов, которые участвуют в текущем наборе
        ArrayList<Integer> indices = new ArrayList<>();
        //запускаем подбор
        recursive(weights, indices);
    }
    //каждый раз запуская эту функцию она увеличивает линну списка индексов на 1, подставляя все возможные элементы на последнее место, и, если какие-то из вариантов подходят - выводит их. 
    private static void recursive(float[] weights, ArrayList<Integer> indices) {
        //если число индексов перевалило за предел - прерываемся 
        if (indices.size() > MAX_EQUIP_COUNT)
            return;
        //если в текущем наборе ничего нет, то начинаем перебор с 0
        int i = 0;
        if (indices.size() > 0)
            //если ест, то берем последний индекс в списке и начинаем перебирать со следующего(+1)
            i = indices.get(indices.size() - 1) + 1;
        //i объявили выше, поэтому между открывающейся скобкой и ; ничего нет
        for (; i < weights.length; i++) {
            //добавляем к списку новый элемент и считаем сумму всех весов, попавших в список
            indices.add(i); 
            float sum = 0;
            for (Integer index : indices) {
                sum += weights[index];
            }
            //считаем разницу между нужной массой и имеющейся. Берем от результата модуль. Если этот модуль меньше epdilon, то наша сумма оооочень близко к нужной, считаем что этого достаточно и мы подобрали нужный результат
            if (Math.abs(sum - REQUIRED_WEIGHT) < epsilon) {
                StringBuilder s = new StringBuilder();
                s.append(weights[indices.get(0)]);
                for(int j = 1; j < indices.size(); j++){
                    s.append(", ").append(weights[indices.get(j)]);
                }
                System.out.println("Подходящая сумма: " + s.toString());
            } else if (sum < REQUIRED_WEIGHT) {
                //если сумма не подобралась - увеличиваем длинну списка индексов на 1
                recursive(weights, indices);
            }
            //в конце удаляем последний элемент, это тот элемент, который мы добавили в начале цикла
            indices.remove(indices.size() - 1);
        }
    }
}
READ ALSO
Как уменьшить/увеличить размер массива

Как уменьшить/увеличить размер массива

Мне в классе нужно создать массив (именно массив, не список) из X элементов, как затем размер этого массива увеличить и уменьшить на 1 элемент...

189
Многопоточное программирование (класс Thread)

Многопоточное программирование (класс Thread)

Решил посмотреть как работает метод start()Не нашел ни одного упоминания о методе run()

113
Заливка области

Заливка области

У меня есть фигура нарисованная через GeneralPath path;

243