0

又一个背包问题......我理解背包问题的概念，但我的部分代码有问题......我想相信我正朝着正确的方向前进，但也许不是？

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。在某种程度上，我理解这个问题使用组合/排列。我只是无法让我的代码按照我想要的方式工作。下面是我的代码。如果我有任何不清楚的地方，请告诉我。

    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;

}
4

1 回答 1

0

所以，我想出了我的问题的答案：如何获得数组中每个元素的组合

我的代码演示了布尔值的使用。使用这个标记为“x”的布尔值，它将遍历我的递归的其余部分，寻找正确的组合，直到 x 应该返回 false。在不向可能被困在我所在位置的人提供答案的情况下，我将给出一个小代码示例。

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

使用这段代码，可以重构上述基本情况，以确定上述代码是返回真还是假。如果它返回真，那么它应该打印出所有加到目标重量的必要数据。如果它返回 false，那么它应该继续到列表中的下一个项目。

要记住的事情：调用这个布尔值并不意味着你会改变“我们的世界”中的任何变量，布尔值所做的是它进入它自己的递归潜水而不实际改变我们最初拥有的任何东西。这就是“展开”递归潜水的想法出现的地方，因为一旦布尔值找到答案，它将展开递归潜水，允许布尔值检查组合而无需更改您的起始位置，除非必要。

于 2013-11-05T18:20:56.557 回答