从一组中查找给出最少量废物的数字 [英] Finding the numbers from a set which give the minimum amount of waste

问题描述

一个集合被传递给下面的这个方法，并且还传入一个条形的长度。解决方案应输出集合中的数字，如果从集合中删除了集合中的某些数字，则会产生最少的浪费。长度。因此，条形长度10，设置包括6,1,4，因此解决方案是6和4，并且浪费是0.我在通过集合回溯的条件有一些麻烦。我也尝试使用浪费的全局变量来帮助回溯方面，但无济于事。

A set is passed to this method below, and a length of a bar is also passed in. The solution should output the numbers from the set which give the minimum amount of waste if certain numbers from the set were removed from the bar length. So, bar length 10, set includes 6,1,4, so the solution is 6 and 4, and the wastage is 0. Im having some trouble with the conditions to backtrack though the set. Ive also tried to use a wastage "global" variable to help with the backtracking aspect but to no avail.

SetInt是一个手动制作的集合实现，可以添加，删除，检查该集是否为空并从集合中返回最小值。

SetInt is a manually made set implementation, which can add, remove, check if the set is empty and return the minimum value from the set.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package recback;


public class RecBack {

   public static int WASTAGE = 10;

    public static void main(String[] args) {



         int[] nums = {6,1,4};
        //Order Numbers

        int barLength = 10;
        //Bar length

        SetInt possibleOrders = new SetInt(nums.length);
        SetInt solution = new SetInt(nums.length);
        //Set Declarration


        for (int i = 0; i < nums.length; i++)possibleOrders.add(nums[i]);
        //Populate Set

        SetInt result = tryCutting(possibleOrders, solution, barLength);
        result.printNumbers();


    }

    private static SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft)
      {



        SetInt clonedSet = possibleOrders.cloneSet(); //initialise selection of candidates

        for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat
          {

            int a = clonedSet.min(); //select next candidate

            if (a <= lengthleft) //if accecptable
              { 
                solution.add(a); //record candidate
                lengthleft -= a;
                clonedSet.remove(a); //remove from original set

                if (!clonedSet.isEmpty()) //solution not complete
                  {
                    WASTAGE +=a;
                    tryCutting(clonedSet, solution, lengthleft);//try recursive call

                    if (lengthleft > WASTAGE)//if not successfull
                      {
                        WASTAGE += a;
                        solution.remove(a);
                      }

                  } //solution not complete
              }
          } //for loop
        return solution;

      }
  }

推荐答案

你有几个问题。

一行是这一行：
int a = clonedSet.min（）; //选择下一个候选人

如果你走过你的例子，它会找到值1并首先使用它，所以1和4本来会被使用，但是6会不会。

If you walk through your example, it would have found the value 1 and used that first, so 1 and 4 would have been used, but 6 wouldn't.

你最好寻找最大值< =剩余的长度。

You are better looking for the max value that will be <= the remaining length.

此行对我来说也很奇怪：

This line also is odd to me:

WASTAGE + = a;

你应该减去我的想法，为什么要修改一个静态整数？

You should be subtracting I think, and why are you modifying a static integer?

如果这是某事这可能是可变的，那么你应该把它传入，然后当你完成了浪费的数量后再传回，所以你要返回一个新的类，解决方案和浪费的金额。

If this is something that can be mutable, then you should just pass it in, then pass back when you are done what was the amount wasted, so have a new class that you return, the solution and the amount that was wasted.

对于递归，你需要得到你的例子，然后一次走一个，看看它的行为是否符合预期。

For recursion you will want to have your example, then walk through one at a time and see if the behavior it does is what you expect.

你可能想看一下这个循环：

You may want to look at this loop:

for（int i = 0; i< possibleOrders.numberInSet（）; i ++ ）//重复

因为，如果你是递归地做这个，那么如果你有3个可能的解决方案，你最终会做6个测试，我相信，而不是经历三次，这是你所期望的。

As, if you are doing this recursively, then if you have 3 possible solutions, you will end up doing 6 tests, I believe, rather than going through three times, which is what you expect.

如果你删除for循环，你应该仍然没事。请输入打印声明，以便每次都能看到它。

If you remove the for loop you should still be fine. Put in a print statement so you can watch it go through each time.

更新：

根据更多信息，您要做的是收集所有可能的解决方案，然后您可以做的就是完成第一遍，获得以这种方式工作的解决方案。然后，向左或向右移动可能的解决方案，然后再试一次。

Based on more information, what you will want to do is to collect all the possible solutions, then what you can do is to go through and do the first pass, get the solutions that work that way. Then, shift left or right the possible solutions, then try again.

当你完全转移时，你会尝试各种组合，但不是每种可能的组合但是，你可以接受这些解决方案，看看哪个是最优的。

When you have shifted all the way through, you will have tried various combinations, but not every possible combination, but, you can then take those solutions, and see which is optimal.

如果你想测试更多的组合，那么你需要循环删除一个item，这可能是递归的。

If you want to test more of the combinations, then you will need to loop through removing an item, and this could be recursive.

因此，你需要在另一个函数中使用一个递归函数，所以你递归地遍历所有可能的组合，然后递归地寻找一个问题的解决方案。

So, you will need one recursive function inside another one, so you recursively go through all possible combinations, then recursively look to find a solution to the problem.

我认为寻找 max 可能是最好的，但那只是我的直觉感觉，并且可以证明 min 是最好的。

I think looking for the max would probably be best, but that is just my gut feeling, and it could be shown that min is best.

这篇关于从一组中查找给出最少量废物的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！