我的目标是给程序一些项目（字符串）、一个范围和目标百分比，让它给我每个项目的所有可能百分比。例如，假设你去杂货店买了一篮苹果和梨，你想知道使用所有物品可以得到的所有百分比（不是一个完整的解决方案，我是手工完成的）：
{Apple:50, Pears:50}, {Apple:75, Pears:25}, {Apple:90, Pears:10},etc.
如果我在 20-50 的范围内做同样的事情（意味着单个项目可以具有的最高值是 50%，最低是 20%），那么唯一的结果是：（
{Apple:50, Pears:50}因为只有 2 个项目并且不能超过 50 ％ 重量）
我认为它具有与背包问题相似的特征，但有一些很大的差异，因为没有与物品相关的值/重量（但就像背包问题试图将物品放入背包中一样，我正在尝试将值拟合到 target_percent, 100 %）。我也很难应用一般的动态编程思想，因为我不知道如何解决问题（典型的背包问题会建立结果，然后“缓存”结果以重用，但如果我有一个 X 列表项目，我需要在一个范围内使用所有 X 项目）。
我可以通过蛮力做到这一点，但我觉得它的效率不高，因为它只是尝试一切，所以我使用的界限根本没有被用来使其高效（例如，如果苹果是 75%，那么有没有理由 Pear 应该超过 25%..bounds 是列表、范围和 target_percent 的大小..我可能有 20-30 个列表项，范围为 5-20，或者可能有 50 个项目，范围为 1-5..或者介于两者之间的任何事情我都想尽可能快地获得多少完整的结果。我没有在问题中显示 target_percent 部分，因为一旦我了解如何解决问题，我就可以设置它，但基本上所有这些示例假设最多 100%，但有时您的篮子中可能已经有 20% 的橙子，看看如何使用苹果/梨来填满剩下的 80%）。
我的问题是，我该如何处理（我可以查找的任何想法逻辑、示例或代理问题）？动态编程是否适合这个问题，或者我不能把它分解成更小的问题（请记住，因为它总是包含列表中的所有项目，它没有建立）？如果有人能指出我正确的方向，我愿意研究任何可能有帮助的主题（花了 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]);
}
}