Question

在此问题上,我只想简单列出一个项目和范围的列表,并找到组合,允许使用all 项目。

这里举个例子:想象你有4个物品(苹果、梨、桃子、橙子),需要至少20%的篮子内含每个物品,最多含60%。例如,每个物品的25%、25%、25%或30%、30%、20%、20%等等,但0%、0%、50%、50%不能工作,因为规定的分钟比例是20%。

此程序工作正常, 但使用的项目比整个列表中的项目少( 在每个解决方案中, 4个项目, 有些解决方案包含 2 或 3 个项目, 这并不是我想要的 ) 。如果我发送了 4 个项目的列表, 我想要使用所有 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.

我对为什么会发生这种情况感到非常困惑, 但如果我必须打赌的话, 我想这就是我的递归方式, 以列表中的项目数量来计算, 然后在将列表发送回之前要减去一个。它在 < code> 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("*********");

    }
}

我愿意以更好的方式实现我所期待的结果。

P.s.这不是家庭作业,我不是学生;我只是倾向于发现奇怪的代言人问题。

Edit

我包括了整个代码, 但 < a href=> "http://pastebin.com/Fh6nPwrk" rel="nofollow noreferrer" rel= "nofollow noreferrr" 这里的输出也。这是2653个解决方案的一块片段, 其生成量超过我所需要的量。如果您简要地看它, 你就会看到大部分都是正确的, 但是当您越来越低的时候, 你就会看到没有使用所有的值; 我只需要使用所有值的解决方案; 不应该有 0 值内存。

Answer 1

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 ();
    }
}

如果长变量名称比短变量更清楚,则长变量名称更好,但本身的价值并不大。

更具体地说:坚持命名公约,即爪哇的骆驼Case,而不是_funky_underlines。

我对名字和结果都做了这样的研究...

- 我的印象是,总和必须始终是100,不少于100,也不高于100。因此,如果4x20%是最低值,那么最多60%是不可能的。但我理解这些值是可变的,而在其它情况下,你可能有4x10%的最低值,然后,最多60%是有道理的。我没有为此测试代码。

但我从其余部分中减去最小值( 4* 20%) 来分配, 所以您必须添加这些值作为最终结果。

递归分配函数从终止条件开始: 到达最后一个元素。现在, 其余元素( 可能多少) 需要为最后一个元素配置多少。

此外,您将所有可能的值都用于此元素, 并分配其余的值。

update:

我更改了代码以照顾上限, 并简化了一边的例子, 因为现在它只使用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

Edit

update:

友情链接