Как мне рекурсивно решить «классический» алгоритм ранца?

Question

Это моя задача

Задача о ранце - классика в информатике.В своей простейшей форме он включает в себя попытку поместить предметы разного веса в рюкзак, чтобы у рюкзака был общий вес.Вам не нужно вписываться во все предметы.Например, предположим, что вы хотите, чтобы ваш рюкзак весил ровно 20 фунтов, и у вас есть пять предметов весом 11, 8, 7, 6 и 5 фунтов.Для небольшого количества предметов люди довольно хорошо решают эту проблему путем проверки.Таким образом, вы, вероятно, можете понять, что только комбинация из 8, 7 и 5 элементов добавляет до 20.

Я действительно не знаю, с чего начать писать этот алгоритм.Я понимаю рекурсию применительно к факториалам и числам треугольников.Однако я сейчас потерялся.

Answer 1

Что вы пробовали?

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

1. Вы берете предмет
2. вы не принимаете это

Когда вы берете предмет, вы удаляете его из списка и уменьшаете вместимость на вес предмета.

Когда вы не берете предмет, вы удаляете его из списка, но не уменьшаете емкость.

Иногда помогает напечатать, как могут выглядеть рекурсивные вызовы. В этом случае это может выглядеть так:

Calling 11 8 7 6 5  with cap: 20
 +Calling 8 7 6 5  with cap: 20
 |  Calling 7 6 5  with cap: 20
 |    Calling 6 5  with cap: 20
 |      Calling 5  with cap: 20
 |      Result: 5
 |      Calling 5  with cap: 14
 |      Result: 5
 |    Result: 11
 |    Calling 6 5  with cap: 13
 |      Calling 5  with cap: 13
 |      Result: 5
 |      Calling 5  with cap: 7
 |      Result: 5
 |    Result: 11
 |  Result: 18
 |  Calling 7 6 5  with cap: 12
 |    Calling 6 5  with cap: 12
 |      Calling 5  with cap: 12
 |      Result: 5
 |      Calling 5  with cap: 6
 |      Result: 5
 |    Result: 11
 |    Calling 6 5  with cap: 5
 |      Calling 5  with cap: 5
 |      Result: 5
 |    Result: 5
 |  Result: 12
 +Result: 20
  Calling 8 7 6 5  with cap: 9
    Calling 7 6 5  with cap: 9
      Calling 6 5  with cap: 9
        Calling 5  with cap: 9
        Result: 5
        Calling 5  with cap: 3
        Result: 0
      Result: 6
      Calling 6 5  with cap: 2
        Calling 5  with cap: 2
        Result: 0
      Result: 0
    Result: 7
    Calling 7 6 5  with cap: 1
      Calling 6 5  with cap: 1
        Calling 5  with cap: 1
        Result: 0
      Result: 0
    Result: 0
  Result: 8
Result: 20

Я специально показал вызов [8 7 6 5] емкостью 20, что дает результат 20 (8 + 7 + 5).

Обратите внимание, что [8 7 6 5] вызывается дважды: один раз с емкостью 20 (потому что мы не взяли 11) и один раз с емкостью 9 (потому что с действительно взял 11).

Итак, путь к решению:

11 не принимается, вызывая [8 7 6 5] емкостью 20

8 принято, звонит [7 6 5] с емкостью 12 (20 - 8)

7 принято, вызов [6 5] с емкостью 5 (12 - 7)

6 не берется, вызывая [5] с емкостью 5

5 взято, мы на нуле.

Фактический метод в Java может вместить очень мало строк кода.

Поскольку это, очевидно, домашнее задание, я просто помогу вам со скелетом:

private int ukp( final int[] ar, final int cap ) {
    if ( ar.length == 1 ) {
        return ar[0] <= cap ? ar[0] : 0;
    } else {
        final int[] nar = new int[ar.length-1];
        System.arraycopy(ar, 1, nar, 0, nar.length);
        fint int item = ar[0];
        if ( item < cap ) {
            final int left = ...  // fill me: we're not taking the item
            final int took = ...  // fill me: we're taking the item
            return Math.max(took,left);
        } else {
            return ... // fill me: we're not taking the item
        }
    }
}

Я скопировал массив в новый массив, который менее эффективен (но, в любом случае, рекурсия - это не тот путь, если вы ищете производительность), но более «функциональный».

Answer 2

Я должен был сделать это для своей домашней работы, поэтому я протестировал все вышеперечисленные коды (кроме Python), но ни один из них не работает для каждого углового случая.

Это мой код, он работает для каждого углового случая.

static int[] values = new int[] {894, 260, 392, 281, 27};
static int[] weights = new int[] {8, 6, 4, 0, 21};
static int W = 30;

private static int knapsack(int i, int W) {
    if (i < 0) {
        return 0;
    }
    if (weights[i] > W) {
        return knapsack(i-1, W);
    } else {
        return Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
    }
}

public static void main(String[] args) {
System.out.println(knapsack(values.length - 1, W));}

Он не оптимизирован, рекурсия убьет вас, но вы можете использовать простое напоминание, чтобы это исправить. Почему мой код короткий, правильный и простой для понимания? Я только что проверил математическое определение задачи о ранце 0-1 http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

Answer 3

Проблема в основном модифицированная версия классической задачи о ранце для простоты (там нет значений / преимуществ , соответствующих весам) (для фактических: http://en.wikipedia.org/wiki/Knapsack_problem, 0/1 Рюкзак -Несколько пояснений по поводу псевдокода Wiki , Как понять, что проблема с рюкзаком является NP-полной? , Почему проблема с рюкзаком является псевдополиномом? , http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/).

Вот пять вариантов решения этой проблемы в c #:

version1 : Использование динамического программирования (в виде таблицы - с нетерпением находя решения для всех задач сумм, чтобы добраться до финальной) - O (n * W)

версия 2 : использование DP, но версия для напоминания (ленивый - просто поиск решений для всего, что нужно)

версия 3 Использованиерекурсия для демонстрации перекрывающихся подзадач и оптимальной подструктуры

версия 4 рекурсивная (грубая сила) - в основном принятый ответ

версия 5 использование стека№ 4 (демонстрирует удаление)ng tail recursion)

version1 : Использование динамического программирования (в виде таблицы - с нетерпением находя решения для всех суммированных задач, чтобы добраться до финального) - O (n * W)

public bool KnapsackSimplified_DP_Tabulated_Eager(int[] weights, int W)
        {
            this.Validate(weights, W);
            bool[][] DP_Memoization_Cache = new bool[weights.Length + 1][];
            for (int i = 0; i <= weights.Length; i++)
            {
                DP_Memoization_Cache[i] = new bool[W + 1];
            }
            for (int i = 1; i <= weights.Length; i++)
            {
                for (int w = 0; w <= W; w++)
                {
                    /// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
                    /// f(i, w) = False if i <= 0
                    ///           OR True if weights[i-1] == w
                    ///           OR f(i-1, w) if weights[i-1] > w
                    ///           OR f(i-1, w) || f(i-1, w-weights[i-1])
                    if(weights[i-1] == w)
                    {
                        DP_Memoization_Cache[i][w] = true;
                    }
                    else
                    {
                        DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w];
                        if(!DP_Memoization_Cache[i][w])
                        {
                            if (w > weights[i - 1])
                            {
                                DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w - weights[i - 1]];
                            }
                        }
                    }
                }
            }
            return DP_Memoization_Cache[weights.Length][W];
        }

версия 2 : использование DP, но версия для запоминания (ленивый - просто поиск решений для всего, что нужно)

/// <summary>
        /// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
        /// f(i, w) = False if i < 0
        ///           OR True if weights[i] == w
        ///           OR f(i-1, w) if weights[i] > w
        ///           OR f(i-1, w) || f(i-1, w-weights[i])
        /// </summary>
        /// <param name="rowIndexOfCache">
        /// Note, its index of row in the cache
        /// index of given weifhts is indexOfCahce -1 (as it starts from 0)
        /// </param>
        bool KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int w, int i_rowIndexOfCache, bool?[][] DP_Memoization_Cache)
        {
            if(i_rowIndexOfCache < 0)
            {
                return false;
            }
            if(DP_Memoization_Cache[i_rowIndexOfCache][w].HasValue)
            {
                return DP_Memoization_Cache[i_rowIndexOfCache][w].Value;
            }
            int i_weights_index = i_rowIndexOfCache - 1;
            if (weights[i_weights_index] == w)
            {
                //we can just use current weight, so no need to call other recursive methods
                //just return true
                DP_Memoization_Cache[i_rowIndexOfCache][w] = true;
                return true;
            }
            //see if W, can be achieved without using weights[i]
            bool flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
                w, i_rowIndexOfCache - 1);
            DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
            if (flag)
            {
                return true;
            }
            if (w > weights[i_weights_index])
            {
                //see if W-weight[i] can be achieved with rest of the weights
                flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
                    w - weights[i_weights_index], i_rowIndexOfCache - 1);
                DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
            }
            return flag;
        }

где

public bool KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int W)
        {
            this.Validate(weights, W);
            //note 'row' index represents the number of weights been used
            //note 'colum' index represents the weight that can be achived using given 
            //number of weights 'row'
            bool?[][] DP_Memoization_Cache = new bool?[weights.Length+1][];
            for(int i = 0; i<=weights.Length; i++)
            {
                DP_Memoization_Cache[i] = new bool?[W + 1];
                for(int w=0; w<=W; w++)
                {
                    if(i != 0)
                    {
                        DP_Memoization_Cache[i][w] = null;
                    }
                    else
                    {
                        //can't get to weight 'w' using none of the given weights
                        DP_Memoization_Cache[0][w] = false;
                    }
                }
                DP_Memoization_Cache[i][0] = false;
            }
            bool f = this.KnapsackSimplified_DP_Memoization_Lazy(
                weights, w: W, i_rowIndexOfCache: weights.Length, DP_Memoization_Cache: DP_Memoization_Cache);
            Assert.IsTrue(f == DP_Memoization_Cache[weights.Length][W]);
            return f;
        }

версия 3 Идентификация перекрывающихся проблем с подгруппами и оптимальная структура структуры

/// <summary>
        /// f(i, w) = False if i < 0
        ///           OR True if weights[i] == w
        ///           OR f(i-1, w) if weights[i] > w
        ///           OR f(i-1, w) || f(i-1, w-weights[i])
        /// </summary>
        public bool KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W, int i)
        {
            if(i<0)
            {
                //no more weights to traverse
                return false;
            }
            if(weights[i] == W)
            {
                //we can just use current weight, so no need to call other recursive methods
                //just return true
                return true;
            }
            //see if W, can be achieved without using weights[i]
            bool flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
                W, i - 1);
            if(flag)
            {
                return true;
            }
            if(W > weights[i])
            {
                //see if W-weight[i] can be achieved with rest of the weights
                return this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W - weights[i], i - 1);
            }
            return false;
        }

где

public bool KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W)
        {
            this.Validate(weights, W);
            bool f = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W,
                i: weights.Length - 1);
            return f;
        }

версия 4 Грубая сила

private bool KnapsackSimplifiedProblemRecursive(int[] weights, int sum, int currentSum, int index, List<int> itemsInTheKnapsack)
        {
            if (currentSum == sum)
            {
                return true;
            }
            if (currentSum > sum)
            {
                return false;
            }
            if (index >= weights.Length)
            {
                return false;
            }
            itemsInTheKnapsack.Add(weights[index]);
            bool flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: currentSum + weights[index],
                index: index + 1, itemsInTheKnapsack: itemsInTheKnapsack);
            if (!flag)
            {
                itemsInTheKnapsack.Remove(weights[index]);
                flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum, index + 1, itemsInTheKnapsack);
            }
            return flag;
        }
        public bool KnapsackRecursive(int[] weights, int sum, out List<int> knapsack)
        {
            if(sum <= 0)
            {
                throw new ArgumentException("sum should be +ve non zero integer");
            }
            knapsack = new List<int>();
            bool fits = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: 0, index: 0, 
                itemsInTheKnapsack: knapsack);
            return fits;
        }

версия 5: итерационная версия с использованием стека (примечание - та же сложность - с использованием стека - удаление хвостовой рекурсии)

public bool KnapsackIterativeUsingStack(int[] weights, int sum, out List<int> knapsack)
        {
            sum.Throw("sum", s => s <= 0);
            weights.ThrowIfNull("weights");
            weights.Throw("weights", w => (w.Length == 0)
                                  || w.Any(wi => wi < 0));
            var knapsackIndices = new List<int>();
            knapsack = new List<int>();
            Stack<KnapsackStackNode> stack = new Stack<KnapsackStackNode>();
            stack.Push(new KnapsackStackNode() { sumOfWeightsInTheKnapsack = 0, nextItemIndex = 1 });
            stack.Push(new KnapsackStackNode() { sumOfWeightsInTheKnapsack = weights[0], nextItemIndex = 1, includesItemAtCurrentIndex = true });
            knapsackIndices.Add(0);

            while(stack.Count > 0)
            {
                var top = stack.Peek();
                if(top.sumOfWeightsInTheKnapsack == sum)
                {
                    int count = 0;
                    foreach(var index in knapsackIndices)
                    {
                        var w = weights[index];
                        knapsack.Add(w);
                        count += w;
                    }
                    Debug.Assert(count == sum);
                    return true;
                }
                //basically either of the below three cases, we dont need to traverse/explore adjuscent
                // nodes further
                if((top.nextItemIndex == weights.Length) //we reached end, no need to traverse
                    || (top.sumOfWeightsInTheKnapsack > sum) // last added node should not be there
                    || (top.alreadyExploredAdjuscentItems)) //already visted
                {
                    if (top.includesItemAtCurrentIndex)
                    {
                        Debug.Assert(knapsackIndices.Contains(top.nextItemIndex - 1));
                        knapsackIndices.Remove(top.nextItemIndex - 1);
                    }
                    stack.Pop();
                    continue;
                }

                var node1 = new KnapsackStackNode();
                node1.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack;
                node1.nextItemIndex = top.nextItemIndex + 1;
                stack.Push(node1);

                var node2 = new KnapsackStackNode();
                knapsackIndices.Add(top.nextItemIndex);
                node2.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack + weights[top.nextItemIndex];
                node2.nextItemIndex = top.nextItemIndex + 1;
                node2.includesItemAtCurrentIndex = true;
                stack.Push(node2);

                top.alreadyExploredAdjuscentItems = true;
            }
            return false;
        }

где

class KnapsackStackNode
        {
            public int sumOfWeightsInTheKnapsack;
            public int nextItemIndex;
            public bool alreadyExploredAdjuscentItems;
            public bool includesItemAtCurrentIndex;
        }

и юнит-тесты

[TestMethod]
        public void KnapsackSimpliedProblemTests()
        {
            int[] weights = new int[] { 7, 5, 4, 4, 1 };
            List<int> bag = null;
            bool flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 10, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(5));
            Assert.IsTrue(bag.Contains(4));
            Assert.IsTrue(bag.Contains(1));
            Assert.IsTrue(bag.Count == 3);
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 3, knapsack: out bag);
            Assert.IsFalse(flag);
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 7, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(7));
            Assert.IsTrue(bag.Count == 1);
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 1, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(1));
            Assert.IsTrue(bag.Count == 1);

            flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 10);
            Assert.IsTrue(flag);
            flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 3);
            Assert.IsFalse(flag);
            flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 7);
            Assert.IsTrue(flag);
            flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 1);
            Assert.IsTrue(flag);

            flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 10);
            Assert.IsTrue(flag);
            flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 3);
            Assert.IsFalse(flag);
            flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 7);
            Assert.IsTrue(flag);
            flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 1);
            Assert.IsTrue(flag);

            flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 10);
            Assert.IsTrue(flag);
            flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 3);
            Assert.IsFalse(flag);
            flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 7);
            Assert.IsTrue(flag);
            flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 1);
            Assert.IsTrue(flag);


            flag = this.KnapsackRecursive(weights, 10, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(5));
            Assert.IsTrue(bag.Contains(4));
            Assert.IsTrue(bag.Contains(1));
            Assert.IsTrue(bag.Count == 3);
            flag = this.KnapsackRecursive(weights, 3, knapsack: out bag);
            Assert.IsFalse(flag);
            flag = this.KnapsackRecursive(weights, 7, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(7));
            Assert.IsTrue(bag.Count == 1);
            flag = this.KnapsackRecursive(weights, 1, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(1));
            Assert.IsTrue(bag.Count == 1);

            weights = new int[] { 11, 8, 7, 6, 5 };
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 20, knapsack: out bag);
            Assert.IsTrue(bag.Contains(8));
            Assert.IsTrue(bag.Contains(7));
            Assert.IsTrue(bag.Contains(5));
            Assert.IsTrue(bag.Count == 3);
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 27, knapsack: out bag);
            Assert.IsFalse(flag);
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 11, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(11));
            Assert.IsTrue(bag.Count == 1);
            flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 5, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(5));
            Assert.IsTrue(bag.Count == 1);

            flag = this.KnapsackRecursive(weights, 20, knapsack: out bag);
            Assert.IsTrue(bag.Contains(8));
            Assert.IsTrue(bag.Contains(7));
            Assert.IsTrue(bag.Contains(5));
            Assert.IsTrue(bag.Count == 3);
            flag = this.KnapsackRecursive(weights, 27, knapsack: out bag);
            Assert.IsFalse(flag);
            flag = this.KnapsackRecursive(weights, 11, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(11));
            Assert.IsTrue(bag.Count == 1);
            flag = this.KnapsackRecursive(weights, 5, knapsack: out bag);
            Assert.IsTrue(flag);
            Assert.IsTrue(bag.Contains(5));
            Assert.IsTrue(bag.Count == 1);
        }

Answer 4

public class Knapsack {
    public int[] arr = {11,8,7,6,5};
    public int[] retArr = new int[5];
    int i = 0;
    public boolean problem(int sum, int pick) {
        if(pick == arr.length) {
            return false;
        }
        if(arr[pick] < sum) {   
            boolean r = problem(sum - arr[pick], pick+1);           
            if(!r) {
                return problem(sum, pick+1);
            } else {
                retArr[i++] = arr[pick];
                return true;
            }                   
        } else if (arr[pick] > sum) {
            return problem(sum, pick+1);
        } else {
            retArr[i++] = arr[pick];
            return true;
        }
    }

    public static void main(String[] args) {
        Knapsack rk = new Knapsack`enter code here`();
        if(rk.problem(20, 0)) {
            System.out.println("Success " );
            for(int i=0; i < rk.retArr.length; i++)
                System.out.println(rk.retArr[i]);
        }
    }

}

Answer 5

Вот простая рекурсивная реализация (не очень эффективная, но простая в отслеживании).Он находится на Python, OP запрашивает реализацию Java, но перенести его на Java не должно быть слишком сложно, это похоже на просмотр псевдокода.

Основная функция объявляет три параметра: V - это массивзначения, W - массив весов, а C - вместимость рюкзака.

def knapsack(V, W, C):
    return knapsack_aux(V, W, len(V)-1, C)

def knapsack_aux(V, W, i, aW):
    if i == -1 or aW == 0:
        return 0
    elif W[i] > aW:
        return knapsack_aux(V, W, i-1, aW)
    else:
        return max(knapsack_aux(V, W, i-1, aW),
                   V[i] + knapsack_aux(V, W, i-1, aW-W[i]))

Алгоритм максимизирует стоимость предметов, добавляемых в рюкзак, возвращая максимальное значение, достижимое при заданных весах

Answer 6

Еще одна реализация динамического программирования на Java. Я всегда чувствую, что нисходящий DP, используя памятку, гораздо легче понять, чем восходящий DP.

Полный, не требующий пояснений, исполняемый код с использованием данных из этого примера из Википедии :

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Knapsack {

    private static final List<Item> ITEMS = new ArrayList<>();
    private static final Map<Integer, Bag> CACHE = new HashMap<>();
    private static final boolean FINITE_ITEMS = true; //whether an item can be added more than once

    public static void main(String[] args) {
        ITEMS.add(new Item(4, 12, "GREEN"));
        ITEMS.add(new Item(2, 2, "CYAN"));
        ITEMS.add(new Item(2, 1, "GREY"));
        ITEMS.add(new Item(1, 1, "ORANGE"));
        ITEMS.add(new Item(10, 4, "YELLOW"));
        Bag best = bestBagForCapa(15);
        System.out.println(best.toString());
    }

    public static Bag bestBagForCapa(int capa) {
        if (CACHE.containsKey(capa)) return CACHE.get(capa);
        if (capa < 0) return null;
        if (capa == 0) return new Bag(0, 0);

        int currentWeight = -1;
        int currentValue = -1;
        String newItem = null;
        List<String> previousItems = null;
        for (Item p : ITEMS) {
            Bag previous = bestBagForCapa(capa - p.weight);
            if (previous == null) continue;

            int weightSoFar = previous.weight;
            int valueSoFar = previous.value;
            int nextBestValue = 0;
            Item candidateItem = null;
            for (Item candidate : ITEMS) {
                if (FINITE_ITEMS && previous.alreadyHas(candidate)) continue;
                if (weightSoFar + candidate.weight <= capa && nextBestValue < valueSoFar + candidate.value) {
                    candidateItem = candidate;
                    nextBestValue = valueSoFar + candidate.value;
                }
            }

            if (candidateItem != null && nextBestValue > currentValue) {
                currentValue = nextBestValue;
                currentWeight = weightSoFar + candidateItem.weight;
                newItem = candidateItem.name;
                previousItems = previous.contents;
            }
        }

        if (currentWeight <= 0 || currentValue <= 0) throw new RuntimeException("cannot be 0 here");
        Bag bestBag = new Bag(currentWeight, currentValue);
        bestBag.add(previousItems);
        bestBag.add(Collections.singletonList(newItem));
        CACHE.put(capa, bestBag);
        return bestBag;
    }

}

class Item {

    int value;
    int weight;
    String name;

    Item(int value, int weight, String name) {
        this.value = value;
        this.weight = weight;
        this.name = name;
    }

}

class Bag {

    List<String> contents = new ArrayList<>();
    int weight;
    int value;

    boolean alreadyHas(Item item) {
        return contents.contains(item.name);
    }

    @Override
    public String toString() {
        return "weight " + weight + " , value " + value + "\n" + contents.toString(); 
    }

    void add(List<String> name) {
        contents.addAll(name);
    }

    Bag(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

}

Answer 7

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

public class Knapsack {

    public static void main(String[] args) {
        int[] arr = new int[]{11, 8, 7, 6, 5};
        find(arr,20);
    }

    public static boolean find( int[] arr,int total){
        return find(arr,0,total);
    }

    private static boolean find( int[] arr,int start,  int total){
        if (start == arr.length){
            return false;
        }
        int curr = arr[start];
        if (curr == total){
            System.out.println(curr);
            return true;
        }else if (curr > total || !find(arr,start+1,total-curr)){
            return find(arr,start+1,total);
        }
        System.out.println(curr);
        return true;
    }
}

Answer 8

Вот решение Java

static int knapsack(int[] values, int[] weights, int W, int[] tab, int i) {
    if(i>=values.length) return 0;
    if(tab[W] != 0) 
        return tab[W];      

    int value1 = knapsack(values, weights, W, tab, i+1);        
    int value2 = 0;
    if(W >= weights[i]) value2 = knapsack(values, weights, W-weights[i], tab, i+1) + values[i];

    return tab[W] = (value1>value2) ? value1 : value2;
}

Проверьте это с помощью

public static void main(String[] args) {
    int[] values = new int[] {894, 260, 392, 281, 27};
    int[] weights = new int[] {8, 6, 4, 0, 21};
    int W = 30;
    int[] tab = new int[W+1];
    System.out.println(knapsack(values, weights, W, tab, 0));
}