递归背包Java-错误 [英] Recursive Knapsack Java -- Errors

问题描述

还有另一个背包问题...我了解背包问题的概念，但是我在代码的某些部分遇到了麻烦.我想相信自己已经朝着正确的方向前进了，但也许没有?

yet another knapsack question... I understand the concept of the knapsack problem but I am having troubles with parts of my code.. I would like to believe that I am headed into the right direction but maybe not?

Let's say I have a list of 1,2,3,6,7 and my goal weight is 4:
The items that will equal this weight are 1 and 3. 
My first iteration will go like this:
Item: 1
Goal Weight: 3 (I did weight - the item)
Items: 1,2
Goal Weight: 1
Items: 1,2,3
Goal Weight: -2
-- Once the weight reaches < 0, it should restart the goal weight and then restart the position    
but the items should start at 1 and skip over 2, going straight to 3. An Example below:
Items: 1
Goal Weight: 3
Items: 1, 3
Goal Weight: 0 // Finished

-但是，我不知道如何跳过2并转到3.从某种意义上说，我知道此问题使用组合/排列.我只是无法让我的代码按照我想要的方式工作.下面是我的代码.如果我不清楚，请告诉我.

--However, I do not know how skip over the 2 and go to 3. In a way, I understand that this problem uses combinations/permutations. I just can't get my code to work the way I want it to. Below is my code. Please let me know if I am unclear in anything.

    public boolean recursive(int weight, int start){
       if(weight == 0){// if weight is zero, we found what we wanted.
           System.out.println("We did it");
           return true;
       }
       else if(weight < 0){ //Too much weight in the bag.
           if(start == storeItems.length-1){ //reached the end of the array.
           recursive(goalWeight, start + 1);
           return false;
           }
           else{ // did not reach end of the array but still not the right combination of numbers.
              recursive(weight, start + 1);
           }
       }
       else if(weight > 0){
           System.out.println(storeItems[start]);
           boolean x = recursive(weight - storeItems[start], start + 1);
       }else{
           System.out.print("No values");
       }
    return false;

}

推荐答案

因此，我想出了我的问题的答案:如何获取数组中每个元素的组合

So, I figured out the answer to my question: How can I get a combination of each element in my array

我的代码演示了布尔值的用法.使用标记为"x"的布尔值，它将遍历我的其余递归，寻找正确的组合，直到x应该返回false.在不向可能被困在我身旁的人提供答案的情况下，我将举一个小代码示例.

My code demonstrates the use of a boolean. With this boolean labeled 'x', it will traverse the rest of my recursion, looking for the correct combination until x should return false. Without giving away the answer to people who were potentially stuck where I was, I will give a small code example.

boolean x = recursive(weight - storeItems[start], start + 1)

使用这段代码，可以重构上述基本情况，以确定上面的代码将返回true还是false.如果返回true，则应打印出加总到目标权重的所有必要数据.如果返回false，则应继续执行列表中的下一项.

Using this piece of code, one can restructure the above base cases to determine whether the above piece of code will return true or false. If it returns true, then it should print out all of the necessary data that added up to the goal weight. If it returns false, then it should continue to the next item in the list.

注意事项: 称为布尔值并不意味着您将更改我们的世界"中的任何变量，布尔值所做的是将其放入自己的递归潜水中，而实际上并未更改我们最初拥有的任何内容.这就是释放"递归潜水的想法的地方，因为一旦布尔值找到答案，它将解散递归潜水，允许布尔值检查组合而无需更改起始位置，除非必要.

Things to keep in mind: Calling this boolean does not mean you will alter any variables in "our world", what the boolean does is it goes into it's own recursive dive without actually altering anything we originally had. This is where the thought of "unwinding" a recursive dive comes in, because once the boolean finds its answer, it will unwind the recursive dive, allowing the boolean to check the combinations without ever changing your start position unless necessary.

这篇关于递归背包Java-错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！