在这个问题中，我试图简单地获取一个项目列表和一个范围，并找到允许使用所有项目的组合。

举个例子:假设您有 4 件元素(苹果、梨、桃子和橙子)，并且希望每件元素至少占篮子的 20%，最多占 60%。例如，您可以有 25%、25%、25%、25% 或 30%、30%、20%、20% 等，但 0%、0%、50%、50% 不会工作，因为指定的最小百分比是 20%。

该程序运行良好，但它使用的项目少于整个列表(而不是每个解决方案中的 4 个项目，有些解决方案包含 2 或 3 个项目，这不是我想要的)。如果我发送 4 个项目的列表，我希望将所有 4 个项目一起使用的组合，仅此而已。我不想要这个，因为我计划使用大列表，并且我希望大小是过去只用于全部且不小于最小值的项目。下面是一个使用上述信息的示例(4 项，20-60% 范围):

good:
 apples = 22
 pears  = 24
 peach  = 25
 orange = 29
 total: 100%

bad:
 apples = 0
 pears  = 0
 peach  = 40
 orange = 60
 total: 100%
 // Although total is correct, the example fails because
 // the minimum of 20% per item was not obeyed.

我真的很困惑为什么会发生这种情况，但如果非要我打赌的话，我认为这是我的递归方式，即获取列表中的项目数并在将其发回之前减去一个。它在方法 recursion_part 中:

private static void recursion_part(int k, int sum, int[] coeff) {
    //k is number of items in the list(in this example its 4(0-3), sum is the remaining total percent to break down, coeff is the template to store values
    //this recursively takes the sum and tries to find lower values of it until it equals zero using the bounds given
    for (int c = low_bound[k]; c <= high_bound[k]; c++) {  
        coeff[k] = c;
        int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
        if (c - sum == 0) {
        results.add(newcoeff);
        printresults(newcoeff);
        break;
    } else if (k > 0) {
        recursion_part(k - 1, sum - c, newcoeff);
    }
}
}

我想处理更大的列表，我认为如果它计算出很多我不关心的结果，那将是一个问题。我如何重新设计它以仅处理列表中的所有项目并保持在范围限制内？

我想过放置一个方法来检查列表中有多少个零，然后如果它低于列表的大小则中断，但我得到空白结果的事实意味着它的处理项目少于我的列表我认为最好将程序设计为不浪费资源。

这是完整的代码(它按描述工作，但如上所述给出零结果):

import java.util.ArrayList;
import java.util.Arrays;


public class recursion_percent_returner {
    static final int target_percent = 100;
    static final String[] names = new String[] {"apples", "pears", "peach", "orange" };
    static int[] low_bound = new int[names.length];
    static int[] high_bound = new int[names.length];
    static ArrayList results =  new ArrayList(); //queue to store results
    static int[] default_coeff = new int[names.length];
    
    public static void main(String[] args) {
        System.out.println("starting..");
        System.out.println("list size " + names.length);
        Arrays.fill(low_bound, 20); //fills the min list with default value
        Arrays.fill(high_bound, 60); //fills the max list with default value
        recursion_part(names.length-1,target_percent,default_coeff);
        System.out.println("total size of results are " + results.size());
    }

    private static void recursion_part(int k, int sum, int[] coeff) {
        //k is number of items in the list(in this example its 4(0-3), sum is the remaining total percent to break down, coeff is the template to store values
        //this recursively takes the sum and tries to find lower values of it until it equals zero using the bounds given
        for (int c = low_bound[k]; c <= high_bound[k]; c++) {  
            coeff[k] = c;
            int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
            if (c - sum == 0) {
                results.add(newcoeff);
                printresults(newcoeff);
                break;
            } else if (k > 0) {
                recursion_part(k - 1, sum - c, newcoeff);
            }
        }
    }

    private static void printresults(int[] newcoeff) {      
        for (int x = 0; x<newcoeff.length; x++) {
            System.out.println(names[x] + " = " + newcoeff[x]);
        }
        System.out.println("*********");

    }
}

我愿意接受更好的方法来实现我正在寻找的结果。

附注这不是家庭作业，我也不是学生；我只是倾向于发现听起来很奇怪的代理问题。

编辑

我包含了整个代码，但是 here's the output as well .它是 2653 解决方案的一个片段，生成的内容超出了我的需要。如果你简单地看一下，你会发现大部分都是正确的，但是当你看得越来越低时，你会发现并不是所有的值都被使用了；我只想要使用所有值的解决方案；不应有 0 个值条目。

最佳答案

import java.util.*;

public class Distributor {

    private ArrayList<int[]> result =  new ArrayList <int[]> ();
    
    public Distributor (final String [] names, int [] low, int [] high) 
    {
        final int rest = 10;
        int minimum = 0;
        for (int l : low)
            minimum += l; 
        int [] sizes = new int [names.length];
        distribute (0, low, high, rest - minimum, sizes);
        System.out.println ("total size of results are " + result.size ());
        for (int [] ia : result)
            show (ia, low); 
    }
    
    public static void main (String [] args) {
        final String [] names = new String [] {"a", "b", "c"};
        int [] low = new int [] {2, 2, 1};
        int [] high = new int [] {3, 4, 6};
        new Distributor (names, low, high);
    }
    
    /*
        distribute the rest of values over the elements in sizes, beginning with index i.           
    */
    void distribute (int i, int [] low, int [] high, final int rest, int [] sizes) {
        // System.out.println (i + " " + rest + " " + sizes);
        if (i == sizes.length - 1) {
            if (rest < high [i]) {
                sizes[i] = rest; 
                result.add (Arrays.copyOf (sizes, sizes.length));
            }
        }
        else 
            for (int c = 0; 
                c <= java.lang.Math.min (high [i] - low [i], rest); 
                ++c) {  
                sizes [i] = c;
                    distribute (i + 1, low, high, rest - c, sizes);                 
            }
    }

    private static void show (int [] arr, int [] low) {      
        for (int x = 0; x < arr.length; x++) {
            System.out.print (" " + (arr [x] + low[x]));
        }
        System.out.println ();
    }
}

长变量名更好，如果它们比短变量名更清晰。但它们本身并没有更有值(value)。

更重要的是:坚持命名约定，这是 Java 中的 CamelCase，而不是_funky_underlines。

好的 - 为什么 low 和 high 应该是静态的？我没有在“名称”和“结果”的这个方向上努力。保留为删除静态修饰符的练习。

好的 - 我的印象是，总和需要始终为 100，不能少于，也不能超过 100。因此，如果 4x20% 是最小值，那么最大值 60% 是不可能的。但我知道这些值是可变的，在另一个设置中，您可能有最小 4x10%，然后，最大 60% 是有意义的。我没有为此目的测试代码。

但是我用剩下的减去最小值(4*20%)来分配，所以你必须加上这些值才能得到最终结果。

递归分发函数以终止条件开始:到达最后一个元素。现在剩下的 - 它可能是多少 - 必须放在最后一个元素上。

否则，您获取此元素的所有可能值，然后分配其余值。

更新:

我更改了代码以处理上限，并在一方面简化了示例，因为它现在仅使用 3 个元素并且最多使用 10 个而不是 100 个。输出显示实际值(最小值 + 变量部分)，算法只添加不违反上限约束的解。

示例输出:

 2 2 6
 2 3 5
 2 4 4
 3 2 5
 3 3 4
 3 4 3
total size of results are 6

关于java - 设计递归时遇到问题，结果有限，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10760100/