我如何解决“经典”背包algorithmrecursion？

这是我的任务

背包问题是计算机科学中的一个典型问题。 最简单的forms是将不同重量的物品装入背包，使背包以指定的总重量结束。 你不需要适应所有的项目。 例如，假设你想让你的背包重达20磅，而你有五件重量为11,8,7,6和5磅的物品。 对于less数项目，人类通过检查来解决这个问题非常好。 所以你可能会发现，只有8,7和5个项目的组合才会增加到20个。

我真的不知道从哪里开始写这个algorithm。 我理解recursion适用于阶乘和三angular形数字。 不过现在我迷路了。

你尝试了什么？

这个想法，鉴于你所说的问题（它指定我们必须使用recursion）很简单：对于你可以采取的每个项目，看看是否更好采取它。 所以只有两条可能的path：

  1. 你拿这个物品
  2. 你不要接受

当您拿取物品时，将其从列表中移除，并通过物品的重量减less容量。

当你不拿这个项目时，如果你从列表中删除，但不减less容量。

有时它有助于打印recursion调用可能的样子。 在这种情况下，它可能看起来像这样： 

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

我特意做了一个20的容量调用[8 7 6 5]，结果是20（8 + 7 + 5）。

注意[8 7 6 5]被称为两次：一次容量为20（因为我们没有取11），一次容量为9（因为取了11）。

所以解决scheme的path：

11没有采取，呼吁[8 7 6 5]容量为20

8号，以12（20-8）的容量呼叫[7 6 5]

7次，以5（12 – 7）的容量呼叫[6 5]

6没有采取，召唤[5]容量为5

5被采取，我们在零。

Java中的实际方法可以适用于很less的代码行。

由于这显然是功课，我会帮​​你一个骨架： 

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

我没有复制数组到一个新的数组，这是效率较低（但无论如何，recursion是不是去这里如果你寻求性能的方式），但更“function”。

我不得不这样做我的作业，所以我testing了所有上面的代码（Python除外），但没有一个适用于每个angular落的情况。

这是我的代码，适用于每个angular落的情况。 

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

它没有优化，recursion会杀了你，但你可以使用简单的memoization来解决这个问题。 为什么我的代码简洁易懂？ 我刚刚检查了0-1背包问题的math定义http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

问题是简单的经典背包问题的基本修改版本（ 没有价值/福利对应的权重）（实际： http : //en.wikipedia.org/wiki/Knapsack_problem，0/1 背包 – 一些澄清Wiki的伪代码 ， 如何理解背包问题是NP完全的？ ， 为什么背包问题是伪多项式的？ ， 问题是什么？ – 问题解答 – 问题 / ）。

这里有五个版本的解决这个在C＃中：

版本1 ：使用dynamic编程（列表 – 通过热切地find所有总和问题的解决scheme，以达到最终的解决scheme） – O（n * W）

版本2 ：使用DP，但memoization版本（懒 – 只需find解决scheme）

版本3使用recursion来演示重叠的子问题和最佳的子结构

版本4recursion（蛮力） – 基本接受的答案

版本5使用堆栈＃4（展示删除尾recursion）

版本1 ：使用dynamic编程（列表 – 通过热切地find所有总和问题的解决scheme，以达到最终的解决scheme） – 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但记忆版本（懒惰 – 只需find解决scheme） 

 /// <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：迭代版本使用堆栈（注 – 相同的复杂性 – 使用堆栈 – 删除尾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; }

哪里 

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

和unit testing 

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

这是一个简单的recursion实现（效率不高，但易于遵循）。 在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]))

该algorithm最大化添加到背包的项目的值，返回给定权重可达到的最大值 

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

Java中的另一个dynamic编程实现。 我总是觉得自上而下的DP使用memoization比自下而上的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; } }

这是一个Java解决scheme 

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

通过使用testing它 

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

这里是Java中的一个简单的recursion解决scheme，但是如果可能的话，你应该避免使用recursion。 

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

    为什么背包问题是伪多项式？

    如何使用背包algorithm来find包中的元素？