当前位置： 文江博客话题详情

如何解决“经典”问题？背包算法递归？

发布于 2024-12-09 16:59:03 字数 297 浏览 0 评论 0原文

这是我的任务

背包问题是计算机科学中的经典问题。最简单的 它涉及尝试将不同重量的物品放入一个 背包，以便背包最终达到指定的总重量。 您不需要适合所有项目。例如，假设您想要 你的背包重量正好是 20 磅，你有五件物品， 重量为 11、8、7、6 和 5 磅。对于少量物品， 人类非常擅长通过检查来解决这个问题。所以你 大概可以算出只有 8、7、5 项的组合 加起来是 20。

我真的不知道从哪里开始写这个算法。我理解应用于阶乘和三角数的递归。然而我现在迷路了。

原文

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.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（10）

有深☉意 2024-12-16 16:59:03

你尝试了什么？

考虑到您所说的问题（指定我们必须使用递归），这个想法很简单：对于您可以采取的每一项，看看是否采取它更好。因此，只有两种可能的路径：

  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（因为 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
        }
    }
}

我确实将数组复制到一个新数组，这效率较低（但无论如何，如果您寻求性能，递归不是这里的方法），但更多“功能性”。

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:

  1. you take the item
  2. 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".

回复 原文
云胡 2024-12-16 16:59:03

我必须为我的家庭作业执行此操作，因此我测试了上述所有代码（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#动态编程

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

回复 原文
意犹 2024-12-16 16:59:03

为了简单起见，该问题基本上是经典背包问题的修改版本（没有与权重对应的值/好处）（实际情况：http://en.wikipedia.org/wiki/Knapsack_problem, 0/1 Knapsack - 对 Wiki 伪代码的一些说明< /a>, 如何理解背包问题是NP完全问题？, 为什么背包问题伪多项式？， http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/）。

以下是在 C# 中解决此问题的五个版本：

版本 1：使用动态规划（列表 - 通过急切地找到所有求和问题的解决方案以达到最终的结果）- O(n * W)

版本2：使用DP但记忆版本（懒惰 - 只是找到所需的解决方案）

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

版本4 > 递归（强力） - 基本上接受的答案

版本5使用#4堆栈（演示删除尾递归）

版本1：使用动态编程（列表 - 通过急切地寻找所有总和的解决方案到达最后一个的问题） - 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;
        }

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

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

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);
        }
回复 原文
无名指的心愿 2024-12-16 16:59:03

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

该算法最大化添加到背包中的物品的价值，返回给定重量可达到的最大值

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

回复 原文
自由如风 2024-12-16 16:59:03
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]);
        }
    }

}

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

}
回复 原文
无声情话 2024-12-16 16:59:03

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

}

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

}
回复 原文
久夏青 2024-12-16 16:59:03
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)

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)
回复 原文
○愚か者の日 2024-12-16 16:59:03

这是另一张

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

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));
}
回复 原文
睫毛上残留的泪 2024-12-16 16:59:03

这是一个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));
}

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));
}
回复 原文
夕嗳→ 2024-12-16 16:59:03

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

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;
    }
}
回复 原文
~没有更多了~

关于作者

拥醉

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

missyouangeled

文章 0 评论 0

三生一梦

文章 0 评论 0

压抑⊿情绪

文章 0 评论 0

天涯离梦残月幽梦

文章 0 评论 0

指尖微凉心微凉

文章 0 评论 0

☆獨立☆

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文