Двумерная рекурсивная функция ранца работает *, но * не может сохранить комбинацию элементов - PullRequest
Новая
       57

Двумерная рекурсивная функция ранца работает *, но * не может сохранить комбинацию элементов

0 голосов
/ 06 декабря 2018

Общее объяснение проблем с рюкзаком Википедия - многомерная проблема с рюкзаком

В моем случае 5 типов предметов, бесконечное количество предметов для каждого (имя, вес, объем, стоимость) :

(«Item_1», 61, 61, 5), («Item_2», 46, 39, 29), («Item_3», 38, 38, 25),(«Item_4», 44, 11, 69), («Item_5», 14, 29, 86)

И моя сумка с максимальным объемом из 326 и максимальным вес из 336.

Моя рекурсивная функция (РАБОТАЕТ ХОРОШО): 

    public int put_in(Item[] items, int current_bag_volume, int current_bag_weight, List<Item> current_items_in_bag) {
    if (items == null) return 0;
    for (Item item : items) {
        if (current_bag_volume + item.getVolume() > pack_volume) continue; 
        if (current_bag_weight + item.getWeight() > pack_weight) continue;
        Item[] other_items = deep_copy_no_LE(items, items.length - 1);
        return Math.max(put_in(other_items, current_bag_volume, current_bag_weight, current_items_in_bag),
                item.getValue() + put_in(items, current_bag_volume + item.getVolume(),
                        current_bag_weight + item.getWeight(), current_items_in_bag));
    }
    return 0;
}

выход, в данном случае, равен 1067, что составляет Оптимальный (10 предметов из 5 и 3 предмета из 4)

Однако я не могу вспомнить оптимальное сочетание предметов ... Я пытался использовать Список current_items_in_bag безуспешно (рекурсивная ошибка)

Есть предложения о том, как вызвать оптимальную комбинацию для максимизации прибыли (стоимости предметов), которая будет работать с моей рекурсивной функцией?

...