从一组中找到给出最少废物量的数字
||
将一个集合传递到下面的此方法，并且还传递一个条的长度。如果从该条的长度中删除了该集合中的某些数字，则解决方案应该输出该集合中的数字，这些数字将提供最少的浪费。因此，条形长度10，集合包括6,1,4，因此解为6和4，浪费为0。我在通过集合回溯的条件上遇到了一些麻烦。香港专业教育学院也试图使用浪费的“全局”变量来帮助回溯方面，但无济于事。
SetInt是一个手工制作的集合实现，可以添加，删除，检查集合是否为空并从集合中返回最小值。
/*
* 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;
}
}
没有找到相关结果
已邀请:
2 个回复
呈辖玫割善
如果您遍历您的示例，它将找到值1并首先使用该值，因此将使用1和4，但不会使用6。 您最好寻找小于等于剩余长度的最大值。 这行对我也很奇怪：我认为您应该减去，为什么还要修改静态整数？ 如果这是可以改变的，那么您应该将其传递，然后在完成后传递回去，这是浪费的数量，因此您要返回一个新的类，解决方案和浪费的数量。 对于递归，您将需要一个示例，然后一次遍历一个示例，看看它的行为是否符合您的期望。 您可能要看一下以下循环：因为，如果您递归执行此操作，那么如果您有3种可能的解决方案，那么我相信您最终将进行6次测试，而不是经过3次测试（这是您期望的）。 如果您删除了for循环，您还是可以的。放入打印声明，以便您每次都能查看。 更新： 根据更多信息，您将要做的是收集所有可能的解决方案，然后您可以做的是经过并进行第一遍，以这种方式获得可行的解决方案。然后，向左或向右移动可能的解决方案，然后重试。 一路转换完后，您将尝试各种组合，但不是每种可能的组合，但是您可以采用这些解决方案，然后看看哪种是最佳的。 如果您想测试更多的组合，则需要遍历删除项，这可能是递归的。 因此，您将需要在另一个函数内部使用一个递归函数，以便您递归地研究所有可能的组合，然后递归地寻找问题的解决方案。 我认为寻找可能是最好的，但这只是我的直觉，可以证明是最好的。茬贺努充尽
public static void main(String[] args) { int[] nums = {6,1,4}; //Order Numbers int barLength = 10; //Bar length bestSolution = new HashSet<SetInt>(); bestWastage = barLength; 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 } tryCutting(possibleOrders, solution, barLength); for (SetInt result : bestSolution) { result.printNumbers(); } } private static int bestWastage; private static Set<SetInt> bestSolution; private static void tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft) { if (lengthleft < bestWastage) { // Better than the best solution bestWastage = lengthleft; bestSolution.clear(); bestSolution.add(solution.cloneSet()); } else if (lengthleft == bestWastage) { // Just as good as the best solution bestSolution.add(solution.cloneSet()); } int a = possibleOrders.min(); //select next candidate if (a <= lengthleft) { // If acceptable possibleOrders.remove(a); // Remove it tryCutting(possibleOrders, solution, lengthleft); // Try without that cut solution.add(a); // add to the solution tryCutting(possibleOrders, solution, lengthleft - a); // Try with that cut solution.remove(a); // remove again possibleOrders.add(a); // add the candidate back on again } }