Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
4elus
0 / 0 / 0
Регистрация: 30.06.2017
Сообщений: 121
1

Рекурсивный перебор

13.12.2018, 04:32. Просмотров 746. Ответов 1
Метки нет (Все метки)

Здравствуйте, решаю задачу о рюкзаке и не могу понять почему возвращает все время 0. Имеется следующий код:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.ArrayList;
 
 
public class Main {
    static ArrayList<Item> items = new ArrayList<>();
    static Backpack bag;
    static final int MAX_WEIGHT = 80;
 
 
    static Item[] goods = {
            new Item("",15, 30),
            new Item("", 30, 90),
            new Item("",50, 100)
    };
 
    public static void main(String[] args) {
        bag = new Backpack(80);
 
        items.add(new Item("Bed", 7, 8));
        items.add(new Item("Chair", 4, 3));
        items.add(new Item("Clock", 2, 9));
 
        //  12 (4, 2)
        System.out.println(combine(items.size()-1, bag.getMaxW()));
 
 
    }
 
    private static double combine(int len, double weight){
        if (len < 0)
            return 0;
        if (items.get(len).getWeight() > weight)
            return combine(len-1, weight);
        else
            return Math.max(combine(len-1, weight), combine(len - 1, weight - items.get(len).getWeight()) + items.get(len).getValue());
    }
 
}
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Item {
    private String name;
    private double weight;
    private double value;
 
    public Item(String name, double weight, double value) {
        this.name = name;
        this.weight = weight;
    }
 
    public String getName() {
        return name;
    }
 
    public double getWeight() {
        return weight;
    }
 
    public double getValue() {
        return value;
    }
 
    public void setWeight(double weight) {
        this.weight = weight;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public void setValue(double value) {
        this.value = value;
    }
}

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.List;
 
public class Backpack {
    private double maxW;
    private double maxC;
    private List<Item> bestItems = null;
 
    public Backpack(double maxW){
        this.maxW = maxW;
 
    }
 
    public double getMaxW(){
        return this.maxW;
    }
 
 
}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2018, 04:32
Ответы с готовыми решениями:

Рекурсивный компаратор
Всем доброго времени суток! Пишу компаратор &quot;рекурсивного действия&quot;. Нужно, чтобы при совпадении...

Рекурсивный метод из нерекурсивного
Добрый день! Имеется задача о рюкзаке в упрощенном виде: необходимо найти предметы, с помощью...

Рекурсивный разворот числа
Здравствуйте. Я новичек в Java. Недавно столкнулся с примером кода, который вогнал меня в ступор: ...

Усовершенствовать рекурсивный алгоритм
Здравствуйте, помогите пожалуйста добавить &quot;кеш&quot; в алгоритм. При больших значения матрицы он не...

Рекурсивный алгоритм вычисления корня из x+1
нужен рекурсивный алгоритм корень из (x +1) , то есть мы вводим число до какого значения х нужно...

1
Thousbe
42 / 18 / 6
Регистрация: 04.05.2013
Сообщений: 48
13.12.2018, 09:25 2
Не надо писать код в
Java
1
public static void main(Stirng[] args)
и делать все методы static из-за этого. Этот метод нужен JVM для запуска приложения, где должен создаваться объект, который будет управлять жизненным циклом программы. Правильнее будет так:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.List;
import java.util.ArrayList;
 
 
public class Main {
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    private List<Item> items;;
    private Backpack bag;
    private final int MAX_WEIGHT = 80;
 
    private Item[] goods = {
            new Item("", 15, 30),
            new Item("", 30, 90),
            new Item("", 50, 100)
    };
 
    public Main() {
        items = new ArrayList<>();
        bag = new Backpack(80);
    }
 
    public void run() {
        items.add(new Item("Bed", 7, 8));
        items.add(new Item("Chair", 4, 3));
        items.add(new Item("Clock", 2, 9));
 
        //  12 (4, 2)
        System.out.println(combine(items.size() - 1, bag.getMaxW()));
    }
 
    private double combine(int len, double weight){
        if (len < 0)
            return 0;
        if (items.get(len).getWeight() > weight)
            return combine(len-1, weight);
        else
            return Math.max(combine(len-1, weight), combine(len - 1, weight - items.get(len).getWeight()) + items.get(len).getValue());
    }
 
}
Также не стоит объявлять список как ArrayList, лучше использовать интерфейс List, и при присваивании задать конкретную реализацию списка.

По поводу вопроса. Всегда возвращается 0, потому что в коде нет другого условия выхода из рекурсии, кроме первого условия
Java
1
2
if (len < 0)
    return 0;
Остальные условие лишь рекурсивно уменьшают len, чтобы вернуть 0.
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2018, 09:25

Как написать рекурсивный метод?
Вот обычный рекурсивный метод, выводящий число Фибоначчи. import java.util.Scanner; ...

Рекурсивный поиск в небинарном дереве
Добрый день! Есть задача реализовать класс, объектом которого является узел дерева (TreeNode). У...

Рекурсивный обход файловой системы
Я ужо замучалась. Мне надо распечатать все файлы и папки с локального диска С. Понимаю, что задача...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.