Рюкзак Решение с использованием рекурсии

Question

Я пытаюсь решить проблему Рюкзак, используя рекурсию в Scala, но мое требование - показать, какие элементы выбраны для хранения в рюкзаке. availableMoney указывает размер рюкзака.

Мой код выглядит следующим образом:

def knapsack(availableMoney: Int,wt:List[Int],value :List[Int] ,n:Int) : Int= { 

    if(n == 0 || availableMoney == 0) 
    return 0 
    if (wt(n - 1) > availableMoney) {  
    return knapsack(availableMoney,wt,value, n - 1) 
    } 
    else { 
    var element1 = value(n-1) + knapsack(availableMoney- wt(n-1), wt, value, n-1) 
    var element2 = knapsack(availableMoney, wt, value, n-1) 

    return max(element1,element2); 
    } 
} 

Как узнать, какие элементы выбраны, чтобы держать в рюкзаке?

Answer 1

Пожалуйста, рассмотреть вопрос о принятии решения amit «S в качестве ответ, я просто хочу добавить дополнительную заметку поверх своего решения здесь.

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

Как указано amit, можно прямо изменить код, чтобы отслеживать элементы в рюкзаке. Ваш метод должен возвращать tuple вместо значения ранца, где первая запись является «максимальным значением» рюкзака, а вторая запись представляет собой список из списка элементов в рюкзаке, который представляет комбинации комбинаций предметов в рюкзаке ,

• Первый if соответствует условию прекращения рекурсии, и есть только одна из возможных комбинаций в рюкзаке - ранец без какого-либо элемента.
• Если условие второго if истинно, тогда элемент n - 1 не может быть выбран, поэтому мы возвращаемся к следующему пункту.
• С другой стороны, если вес товара n - 1 меньше availableMoney, то мы можем либо выбрать пункт n - 1 в строительстве (это соответствует element1), или оставить пункт n - 1 в строительстве.Затем возвращаемое решение должно быть лучшим из двух, или слияние их вместе, если они дают одинаковое значение.

Ниже приводится модифицированная версия кода для справки:

def knapsack(availableMoney: Int, wt: List[Int], value: List[Int], n: Int): (Int, List[List[Int]]) = { 

    if (n == 0 || availableMoney == 0) 
    return (0, List[List[Int]](List[Int]())) 

    if (wt(n - 1) > availableMoney) { 
    return knapsack(availableMoney, wt, value, n - 1) 
    } else { 
    val recur = knapsack(availableMoney - wt(n - 1), wt, value, n - 1) 
    val element1 = (recur._1 + value(n - 1), for (e <- recur._2) yield {e :+ wt(n - 1)}) 
    val element2 = knapsack(availableMoney, wt, value, n - 1) 

    if (element1._1 > element2._1) 
     return element1 
    else if (element1._1 < element2._1) 
     return element2 
    else 
     return (element1._1, element1._2 ::: element2._2) 
    } 
} 

Answer 2

В коде вы уже знаете, был ли выбран текущий элемент или нет.

Если вы выбрали element1 (он выше element2), то был выбран последний элемент (index = n-1). Нет, это не так.

Итак, вы можете добавить еще один выходной аргумент, который будет возвращен из рекурсивного вызова, который укажет на выбранные элементы.

И вам нужно будет изменить все return ... также заботиться о нем:

• return 0 станет return (0,[])
• return knapsack(availableMoney,wt,value, n - 1) остается как есть.
• return max(element1,element2) вернет (element1, list1.add(n-1)) или (element2, list2), в зависимости от чего выше, element или element2.

Кроме того, если вы хотите реализовать как Динамическое программирование, этот вопрос обсуждается, как вернуть элементы, а не только значения:

How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?