How do I solve the 'classic' knapsack algorithm recursively?

Question

This is my task

The Knapsack Problem is a classic in computer science. In its simplest form it involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. You don't need to fit in all the items. For example, suppose you want your knapsack to weigh exactly 20 pounds, and you have five items, with weights of 11, 8, 7, 6, and 5 pounds. For small numbers of items, humans are pretty good at solving this problem by inspection. So you can probably figure out that only the 8, 7, and 5 combination of items adds up to 20.

I really don't know where to begin writing this algorithm. I understand recursion when applied to factorials and triangle numbers. However I'm lost right now.

Dynamic Programming for example. No recursion needed. You may always try to change NP-complete program into pseudo-polynomial, knapsack is one of those problems. — Benjamin, Jun 25 '13 at 22:49
I like to listen experienced-**wise** people before going deeper into a subject. To be skillful on DP, one needs to be skillful on _Recursion, Memoized approach and Bottom-up(Tabulation) approach_. That's why the guy highly likely ponders its recursive way like me. — Soner from The Ottoman Empire, Jan 03 '19 at 17:00
So, @Benjamin's saying is genuinely minute right. No recursion is needed, yet recursion formula is inevitable sine qua non for DP. — Soner from The Ottoman Empire, Jan 03 '19 at 17:05

TacticalCoder · Accepted Answer · 2011-10-15T01:54:56.270

What did you try?

The idea, given the problem you stated (which specifies we must use recursion) is simple: for each item that you can take, see if it's better to take it or not. So there are only two possible path:

you take the item
you don't take it

When you take the item, you remove it from your list and you decrease the capacity by the weight of the item.

When you don't take the item, you remove if from you list but you do not decrease the capacity.

Sometimes it helps to print what the recursive calls may look like. In this case, it could look like this:

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

I did on purpose show the call to [8 7 6 5] with a capacity of 20, which gives a result of 20 (8 + 7 + 5).

Note that [8 7 6 5] is called twice: once with a capacity of 20 (because we didn't take 11) and once with a capacity of 9 (because with did take 11).

So the path to the solution:

11 not taken, calling [8 7 6 5] with a capacity of 20

8 taken, calling [7 6 5] with a capacity of 12 (20 - 8)

7 taken, calling [6 5] with a capacity of 5 (12 - 7)

6 not taken, calling [5] with a capacity of 5

5 taken, we're at zero.

The actual method in Java can fit in very few lines of code.

Since this is obviously homework, I'll just help you with a skeleton:

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
        }
    }
}

I did copy the array to a new array, which is less efficient (but anyway recursion is not the way to go here if you seek performance), but more "functional".

score 17 · Answer 2 · answered Jan 06 '13 at 20:52

I had to do this for my homework so I tested all of the above codes (except for the Python one), but none of them work for every corner case.

This is my code, it works for every corner case.

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));}

It is not optimized, the recursion will kill you, but you can use simple memoization to fix that. Why is my code short, correct and simple to understand? I just checked out the mathematical definition of the 0-1 Knapsack problem http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

Is there a way of keeping track of the unique items you used in this recursion? I've been trying to figure it out for a few hours now with no success. — crashprophet, Feb 24 '14 at 01:06
@crashprophet, [HashSet](http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html) — starscream_disco_party, Apr 28 '15 at 02:47

score 10 · Answer 3 · edited May 23 '17 at 12:02

The problem is basically modified version of classic knapsack problem for simplicity (there are no values/benefits corresponding to weights) (for actual: http://en.wikipedia.org/wiki/Knapsack_problem, 0/1 Knapsack - A few clarification on Wiki's pseudocode, How to understand the knapsack problem is NP-complete?, Why is the knapsack problem pseudo-polynomial?, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/).

Here are five versions of solving this in c#:

version1: Using dynamic programming (tabulated - by eagerly finding solutions for all sum problems to get to final one) - O(n * W)

version 2: Using DP but memoization version (lazy - just finding solutions for whatever is needed)

version 3 Using recursion to demonstrate overlapped sub problems and optimal sub structure

version 4 Recursive (brute force) - basically accepted answer

version 5 Using stack of #4 (demonstrating removing tail recursion)

version1: Using dynamic programming (tabulated - by eagerly finding solutions for all sum problems to get to final one) - 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];
        }

version 2: Using DP but memorization version (lazy - just finding solutions for whatever is needed)

/// <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;
        }

where

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;
        }

version 3 Identifying overlapped sub problems and optimal sub structure

/// <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;
        }

where

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;
        }

version 4 Brute force

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;
        }

version 5: Iterative version using stack (note - same complexity - using stack - removing tail recursion)

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;
        }

where

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

And unit tests

[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);
        }

score 2 · Answer 4 · answered Aug 02 '13 at 19:37

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]);
        }
    }

}

Óscar López · Answer 5 · 2011-10-15T00:32:17.713

2

Here's a simple recursive implementation (not very efficient, but easy to follow). It's in Python, OP is asking for a Java implementation, but porting it to Java shouldn't be too difficult, it's like looking at pseudo-code.

The main function declares three parameters: V is an array of values, W is an array of weights and C the capacity of the knapsack.

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]))

The algorithm maximizes the value of the items added to the knapsack, returning the maximum value attainable with the given weights

edited Oct 15 '11 at 00:32

answered Oct 15 '11 at 00:26

Óscar López

232,561
37
312
386

Thanks but I still don't see it. – lampShade Oct 15 '11 at 01:16
@Óscar López: you have answered the "real" knapsack but not his problem, which seems simpler since that there's apparently no value/weight distinction in the OP's problem. – TacticalCoder Oct 15 '11 at 01:48
What do you mean by values? You have a W for weight next to it so it can't be weight. – cokedude Oct 13 '13 at 21:49
@cokedude "V is an array of values". What gets maximized it's the values from this array – Óscar López Oct 14 '13 at 00:53
@ÓscarLópez, I run your code as "knapsack([2, 3], [1, 2], 2)" and received 3 as an output. Are you sure it is working correctly? Or am I missing something? I expected 4, because we can take first element with weight 1 and value 2 twice. – Hasek Oct 11 '17 at 14:51
1

@Hasek you can’t take the same element twice ;) – Óscar López Oct 11 '17 at 14:58

score 0 · Answer 6 · answered Apr 28 '14 at 02:27

Yet another dynamic programming implementation in Java. I always feel top-down DP using memoization is much easier to understand than bottom up DP.

Complete, self-explanatory, runnable code, using data from this example from Wikipedia:

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;
    }

}

score 0 · Answer 7 · answered Jan 13 '20 at 05:42

def knpsack(weight , value , k , index=0 , currweight=0):
    if(index>=len(weight)):
        return 0
take = 0
dontake = 0
if(currweight+weight[index] <= k):
    take = value[index]  + 
         knpsack(weight,value,k,index+1,currweight+weight[index])
dontake = knpsack(weight,value,k,index+1,currweight)
return max(take,dontake)

score 0 · Answer 8 · answered May 22 '23 at 19:51

Here is another one

    static int[] values = new int[] {1,3,5,6};
static int[] weights = new int[] {2,3,4,5};
static int W = 8;

private static int calculate(int i, int W, int cur) {
    // this second check on wts is required so that if there is no space if we try this weight, dont proceed
    if (i == values.length || W - weights[i] <= 0) return cur;
    return Math.max(calculate(i+1, W, cur), calculate(i+1, W - weights[i], cur + values[i]));
}

public static void main(String[] args) {
    System.out.println(calculate(0, W, 0));
}

score -1 · Answer 9 · answered Jun 12 '12 at 05:29

Here is a simple recursive solution in Java but you should avoid using recursion if possible.

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;
    }
}

score -1 · Answer 10 · answered Feb 24 '12 at 23:12

Here is a Java solution

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;
}

Test it by using

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));
}

How do I solve the 'classic' knapsack algorithm recursively?

10 Answers10

Linked