java - 创建所有可能的项目百分比列表？

Question

我的目标是为程序提供一些项目(字符串)、范围和目标百分比，并让它为我提供每个项目的所有可能百分比。例如，假设您去杂货店，有一篮子苹果和梨，您想知道使用所有元素可以获得的所有百分比(不是完整的解决方案，我是手工完成的): {苹果:50，梨:50}，{苹果:75，梨:25}，{苹果:90，梨:10}等

如果我在 20-50 的范围内做同样的事情(意味着单个项目可以拥有的最高值是 50%，最低值是 20%)，那么唯一的结果是: {Apple:50, Pears:50}(因为只有 2 件商品，重量不能超过 50%)

我认为它具有与背包问题类似的特征，但有一些很大的差异，因为没有与元素相关的值/权重(但就像试图将元素放入背包中的背包问题一样，我试图将值放入背包中)目标百分比，100%)。我在应用一般动态编程思想时也遇到了麻烦，因为我不知道如何分解问题(典型的背包问题建立结果，然后“缓存”结果以重用，但如果我有一个 X 列表项，我需要在一个范围内使用所有 X 项)。

我可以通过蛮力做到这一点，但我不觉得它高效，因为它只是尝试一切，所以我使用的界限根本没有被用来提高它的效率(例如，如果苹果是 75 % 那么 Pear 没有理由应该超过 25%..bounds 是列表、范围和 target_percent 的大小..我可能有 20-30 个列表项，范围为 5-20，或者可能有 50 个列表项，范围为 1-5 ..或者介于两者之间的任何东西我想尝试一下我能尽快获得多少个完整的结果。我没有在问题中显示 target_percent 部分，因为我可以设置它，一旦我了解如何解决问题，但基本上所有示例都假设最大 100%，但有时您的篮子里可能已经有 20% 的橙子，看看如何使用苹果/梨来填满剩余的 80%)。

我的问题是，我该如何解决这个问题(我可以查找任何要使用的想法逻辑、示例或代理问题)？动态编程是否适合这个问题，或者我不能将其分解为更小的 block 这一事实是一个问题(请记住，因为它总是包含列表中的所有项目，所以它不会建立)？如果有人能给我指出正确的方向，我愿意研究任何可能有帮助的主题(在花了 2 天试图弄清楚这一点之后，我只是不确定动态编程路线是否正确)。此类问题是否有一个名称(我查找了背包问题、整数分区、组合问题，但似乎都不合适)？

这是我的(损坏的)暴力方法(它实际上并没有按预期工作，但也许可以让您了解暴力方法):

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


public class brute_force_percent_returner {
    static String[] data = new String[]{"Apple", "Pears"};
    static int[] coeff = new int[data.length];
    static ArrayList<int[]> queue = new ArrayList<int[]>();

    public static void main(String[] args) {
        System.out.println("Starting");
        recursion(0,data);
        for (int[] item : queue) {
            for (int item2 = 0; item2<data.length; item2++) {
                System.out.print(data[item2] + " = " + item[item2] + " ");
            }
            System.out.println();
        }
    }

    private static void recursion(int k, String[] data2) {
        // this is not exactly working
        for (String item: data2) {
            for (int x = 0; x<5;x++) {
                int[] coeff_temp = Arrays.copyOf(coeff, coeff.length);
                coeff_temp[k] = x;
                queue.add(coeff_temp);
            }
        }
        if (k == data.length-1) {
            return;
        } else {
            recursion(k+1, data2);
        }
    }
}

如果它有助于我试图创建的解决方案在某种程度上基于此(它是一个背包问题，但对于大量变量来说似乎非常快，但在这种情况下，其处理的项目是列表中的项目，而就我而言，列表只是字符串):

public class TurboAdder {
    private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 };

    private static class Node {
        public final int index;
        public final int count;
        public final Node prevInList;
        public final int prevSum;
        public Node(int index, int count, Node prevInList, int prevSum) {
            this.index = index;
            this.count = count;
            this.prevInList = prevInList;
            this.prevSum = prevSum;
        }
    }

    private static int target = 100;
    private static Node sums[] = new Node[target+1];

    // Only for use by printString.
    private static boolean forbiddenValues[] = new boolean[data.length];

    public static void printString(String prev, Node n) {
        if (n == null) {
            System.out.println(prev);
        } else {
            while (n != null) {
                int idx = n.index;
                // We prevent recursion on a value already seen.
                if (!forbiddenValues[idx]) {
                    forbiddenValues[idx] = true;
                    printString((prev == null ? "" : (prev+" + "))+data[idx]+"*"+n.count, sums[n.prevSum]);
                    forbiddenValues[idx] = false;
                }
                n = n.prevInList;
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < data.length; i++) {
            int value = data[i];
            for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) {
                for (int newsum = sum+1; newsum <= target; newsum++) {
                    if (sums[newsum - sum] != null) {
                        sums[newsum] = new Node(i, count, sums[newsum], newsum - sum);
                    }
                }
            }
            for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) {
                sums[sum] = new Node(i, count, sums[sum], 0);
            }
        }
        printString(null, sums[target]);

    }
}

Answer 1

这听起来像是家庭作业，所以我不太愿意帮助你太多，但这里有一个方法。

要定义范围，请创建几个 HashMap ，例如

lower bounds = {apples  => 20, pears => 40,  oranges => 0}
upper bounds = {apples  => 50, pears => 100, oranges => 30}

如果您考虑一下，每个最终(有效)组合至少都具有下限映射定义的内容。所以称之为基础组合。

接下来，计算出您可以添加到基本组合中的每种类型的理论最大值。这只是另一张 map

{apples  => 30, pears => 60,  oranges => 30}

计算可以添加到 basemap 的总项目数，即 100 - 所有下限值的总和，在示例中为 40。

现在，您需要生成组合。您可能会发现递归是最简单的方法。我将使用伪代码和硬编码内容演示剩余的算法，以提高清晰度，尽管您需要编写它的通用递归版本。

totalItemsToAdd = 40 //as calculated via baseCombo.sumOfEntries()


for (i=0; i<maxApples; i++) {
    combo = clone the base combination
    combo.apples += i;
    remainingItemsToAdd = totalItemsToAdd - i;
    if (remainingItemsToAdd > 0) {
        for (j=0; j<maxPears; j++) {
            combo.pears += j;
            // and so on, recursively
        }
    }

    results.append(combo)
}

注意它如何通过跟踪每个组合可能有多少个项目来仅生成有效的组合。因此，这不是蛮力，它实际上会做生成组合集所需的最少工作。