如何递归地解决“经典”背包算法？
如何递归地解决“经典”背包算法？
提问于 2011-10-15 00:01:28
这是我的任务
背包问题是计算机科学中的经典问题。在最简单的形式中，它涉及到尝试将不同重量的项目放入背包中，以便背包最终具有指定的总重量。你不需要把所有的东西都放进去。例如，假设你想要你的背包重20磅，你有5个项目，重量分别是11、8、7、6和5磅。对于少量的物品，人类很擅长通过检查来解决这个问题。因此，您可能会发现，只有8、7和5项的组合加起来才有20项。
我真的不知道从哪里开始写这个算法。当应用于阶乘和三角形数时，我理解递归。但是我现在迷路了。
回答 8
Stack Overflow用户
回答已采纳
发布于 2011-10-15 01:46:18
你试过什么？
考虑到您提到的问题(它指定我们必须使用递归)，这个想法很简单:对于您可以接受的每一项，看看是否接受它更好。因此，只有两种可能的途径：
，
- ，你拿着
- ，你不拿
当您取下该项目时，您将其从列表中删除，并根据项目的权重降低其容量。
如果不接受该项目，则从列表中删除“如果”，但不会降低容量。
有时，它有助于打印递归调用的外观。在这种情况下，它可能如下所示：
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(因为with需要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
}
}
}我确实将数组复制到一个新数组中，该数组的效率较低(但是，如果您寻求性能，递归并不是这里的方法)，而是更多的“功能”。
Stack Overflow用户
发布于 2013-01-06 20:52:32
我不得不这样做我的家庭作业，所以我测试了上述所有的代码(除了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的数学定义。
Stack Overflow用户
发布于 2014-07-22 01:56:56
这个问题基本上是简单的经典背包问题的修改版本(没有与权重相对应的值/好处)(对于实际的：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/)。
下面是在c#中解决这个问题的五个版本：
version1：使用动态规划(表-通过急切地为所有和问题找到最终解)- O(n * W)
第2版：使用DP但回忆录版本(懒散-只是找到任何需要的解决方案)
第3版使用递归演示重叠子问题和优化子结构
版本4递归(蛮力)-基本接受答案
使用#4堆栈的版本5 (演示删除尾递归)
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);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7774769
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号