我的目标是让程序几个项目（弦乐），一个范围，并针对％，而让它给我的每个项目的所有可能的百分比。例如，想象一下你去杂货店，并有一篮苹果和放大器;你想知道你可以在使用的所有项目（不是一个完整的解决方案，我这样做手工）百分比梨： {苹果：50，梨子：50}，{苹果：75，梨子：25}，{苹果：90，梨子：10}，等等

如果我做同样的事情，射程20-50（意为最高价值的单个项目可以是50％，最低20％），那么唯一的结果就是： {苹果：50，梨子：50} （因为只有2项，它不能超过50％重量）

我觉得它有相似的特征作为一个背包问题有几个很大的不同，因为有与项目关联的值/重量（但像背包问题的尝试，以适应在一个背包的项目，我想在一个合适的值的target_percent，100％）。我也有适用一般动态规划的思想，以及因为我无法弄清楚如何突破问题分解麻烦（典型背包问题建立的结果，然后缓存的结果重用，但如果如果我有X的列表项目，我需要所有的X项目是一个范围内使用）。

我可以通过蛮力做到这一点，但我不喜欢它的效率，因为它只是尝试一切，让我使用的边界没有被使用，使之有效地在所有（例如，如果苹果75 ％，则没有理由梨不应超过25％..界的列表，范围大小，以及target_percent..I可能有一个范围从1-5，射程5-20或者50项20-30列表项..或在两者之间我想玩弄我多少完整的结果可以得到尽可能快的。我没有表现出的target_percent部分的问题，因为我可以将它设置任何东西，一旦我知道如何解决这个问题，但基本上所有的例子假定100％最大，但有时你可能已经在你的篮子20％的橙子，看看如何使用苹果/梨，以填补剩下的80％）。

我的问题是，我该如何处理这个（任何想法的逻辑来使用，例子或代理问题，我可以看一下）？是动态规划适合于这个问题，或事实，我不能打破成更小吸盘这是一个问题（请记住，因为它总是包含列表中的所有项目，它不是建立）？如果有人能指点正确的方向，我愿意研究任何可能的帮助主题（花2个天尝试算出这个之后，我只是不知道，如果动态规划的路线是正确的）。也有这种类型的问题，一个名字（我抬头背包问题，整数分割，组合，但他们都不似乎适合）？

下面是我的（碎）蛮力方法（它实际上没有按预期工作，但也许给你的蛮力方法的想法）：

 进口的java.util.ArrayList;
进口java.util.Arrays中;


公共类brute_force_percent_returner {
    静态的String []数据=新的String [] {苹果，梨};
    静态INT [] COEFF =新INT [data.length]
    静态的ArrayList＆LT; INT [] GT;队列=新的ArrayList＆其中; INT []≥（）;

    公共静态无效的主要（字串[] args）{
        的System.out.println（启动）;
        递归（0，数据）;
        对于（INT []项目：队列）{
            对于（INT项目2 = 0;项目2＆LT; data.length; ITEM2 ++）{
                System.out.print（数据[项目2] +=+项目[项目2] +）;
            }
            的System.out.println（）;
        }
    }

    私有静态无效递归（INT K，的String []数据2）{
        //这是不完全的工作
        对于（字符串项：数据2）{
            为（中间体X = 0 X  - 其中R 5; X ++）{
                INT [] coeff_temp = Arrays.copyOf（COEFF，coeff.length）;
                coeff_temp [K] = X;
                queue.add（coeff_temp）;
            }
        }
        如果（K == data.length-1）{
            返回;
        } 其他 {
            递归第（k + 1，数据2）;
        }
    }
}
 

如果它有助于解决方案，我试图创建是有点基于这一个（它的一个背包问题，但似乎是超快速的大量的变量，但在这照顾这两个项目的处理都在，而列表中的项目在我的情况的名单只是字符串）：

 公共类TurboAdder {
    私有静态最终诠释[]数据=新的INT [] {5，10，20，25，40，50};

    私有静态类节点{
        公众最终诠释指数;
        公众最终诠释计数;
        公共最后一个节点prevInList;
        公众最终诠释prevSum;
        公共节点（INT指数，诠释计数，节点prevInList，诠释prevSum）{
            this.index =指数;
            this.count =计数;
            这prevInList = prevInList。
            这prevSum = prevSum。
        }
    }

    私有静态诠释目标= 100;
    私有静态节点款项[] =新节点[目标+ 1];

    //只有通过PRINTSTRING使用。
    私有静态布尔forbiddenValues​​ [] =新的布尔[data.length]

    公共静态无效PRINTSTRING（字符串preV，节点n）{
        如果（N == NULL）{
            的System.out.println（preV）;
        } 其他 {
            而（N！= NULL）{
                INT IDX = n.index;
                //我们p $ pvent递归上已经出现了价值为。
                如果（！forbiddenValues​​ [IDX]）{
                    forbiddenValues​​ [IDX] = TRUE;
                    PRINTSTRING（（$ P $光伏== NULL：（preV ++））+数据[IDX] +*+ n.count，款项[ñprevSum]）;
                    forbiddenValues​​ [IDX] = FALSE;
                }
                N = N prevInList。
            }
        }
    }

    公共静态无效的主要（字串[] args）{
        的for（int i = 0; I＆LT; data.length;我++）{
            int值=数据[I]
            对于（诠释计数= 1，总和=值; COUNT＆LT; = 100安培;＆安培;总和＆LT; =目标;计数++，总和+ =值）{
                对于（INT newsum =总和+ 1; newsum＆LT; =目标; newsum ++）{
                    如果（总和[newsum  - 总和]！= NULL）{
                        款项[newsum] =新的节点（i，计数，总和[newsum]，newsum  - 总和）;
                    }
                }
            }
            对于（诠释计数= 1，总和=值; COUNT＆LT; = 100安培;＆安培;总和＆LT; =目标;计数++，总和+ =值）{
                款项[总和] =新的节点（i，计数，总和[总和]，0）;
            }
        }
        PRINTSTRING（空，款项[目标]）;

    }
}
 

解决方案

这听起来像功课，所以我额外不愿意帮你太多，但这里的一种方法。

定义范围，使一对夫妇的哈希映射，像

 下限= {苹果=＆GT; 20，梨=＆GT; 40，橘子=＆GT; 0}
上限= {苹果=＆GT; 50，梨=＆GT; 100，橘子=＆GT; 30}
 

如果你想想看，每一个最终的（有效）组合将最起码，具有由下界映射中定义的内容。故称该基地结合。

接下来，计算出每一种类型可以潜在地添加到基础组合的理论最大值。这仅仅是另一个地图

  {苹果=＆GT; 30，梨=＆GT; 60，橘子=＆GT; 30}
 

图中，可以多少总项目添加到基本地图，这是100 - 所有下界值的总和，在示例其40

现在，您需要生成的组合。你可能会发现递归做到这一点最简单的方法。病人表现出伪code和硬codeD的东西，其余的算法，以提高清晰度，虽然你需要写它的一个通用的，递归版本。

  totalItemsToAdd = 40 //经由baseCombo.sumOfEntries计算（）


对于（i = 0; I＆LT; maxApples;我++）{
    组合=克隆基组合
    combo.apples + =我;
    remainingItemsToAdd = totalItemsToAdd  - 我;
    如果（remainingItemsToAdd大于0）{
        为（J = 0; J＆LT; maxPears; J ++）{
            combo.pears + = j的;
            //等等，递归
        }
    }

    results.append（二合一）
}
 

注意它是如何通过保持多少更多的项目是可能为每个组合的轨道只产生有效组合。所以，这不会是蛮力，和它实际上做需要产生该组的组合的最小工作

My goal is to give the program a few items(Strings), a range, and target percent and let it give me all possible percentages of each item. For example, Imagine you go to the grocery store and have a basket of Apples & Pears you want to know all the percentages you could have using ALL items(not a full solution, I'm doing this by hand): {Apple:50, Pears:50}, {Apple:75, Pears:25}, {Apple:90, Pears:10},etc.

If I do the same thing with a range of 20-50(meaning the highest value a single item can have is 50% and the lowest 20%) then the only result is: {Apple:50, Pears:50} (since there are only 2 items and it cannot exceed 50% weight)

I thought it had similar traits as an knapsack problem with a few big differences since there are no values/weights associated with the items(but like knapsack problem trying to fit items in a knapsack I’m trying to fit values within a target_percent, 100%). I’m also having trouble applying general dynamic programming ideas as well since I can’t figure out how to break the problem down(typical knapsack problems build up results and then ‘cache’ results to reuse but if if I have a list of X items, I need all X items to be used within a range).

I can do this via brute force but I don’t feel like its efficient because it just tries everything so the bounds that I’m using aren’t being used to make it efficient at all(for example if apple is 75% then there’s no reason Pear should exceed 25%..bounds are size of list, range, and target_percent..I might have 20-30 list items with a range of 5-20 or maybe 50 items with a range from 1-5..or anything in between I want to play around with how many complete results I can get as fast as possible. I have not shown the target_percent part in the question because I can set it up that once I understand how to solve the problem, but basically all the examples assume 100% max, but sometimes you may already have 20% oranges in your basket and see how you can use Apples/Pears to fill up the rest 80%).

My questions are, How can I approach this(any ideas logic to use, examples or proxy problems I can look up)? Is dynamic programming appropriate for this problem or the fact that I cannot break this into smaller chucks a problem(remember because its always includes all items in the list, its not building up)? If someone can point me to the right direction, I’m willing to study any topics that might help(After spending 2 days trying to figure this out,I’m just not sure if the Dynamic programming route is correct). Also is there a name for this type of problem(I looked up knapsack problems, integer partitioning, combinatorics but none of them seemed to fit)?

Here's my(broken) brute force approach(its not actually working as expected but maybe gives you an idea of the brute force method):

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

If it helps the solution I was trying to create was somewhat based on this one(its a knapsack problem but seems to be super quick for large number of variables but in this care the items its processing are the items in the list whereas in my case the list is just strings):

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]);

    }
}

This sounds like homework so I'm extra reluctant to help you too much, but here's an approach.

to define the ranges, make a couple hash maps, like

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

if you think about it, every final (valid) combination would at the very least, have the contents defined by the lower bound map. so call that the base combination.

next, figure out the theoretical max of each type you can potentially add to the base combination. this is just another map

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

figure how many total items you can add to the base map, which is 100 - the sum of all the lower bound values, in the example its 40.

now, you need to generate the combinations. You'll probably find recursion the easiest way to do it. ill demonstrate the remaining algorithm with pseudo code and hardcoded stuff to improve clarity, although you'll need to write a generic, recursive version of it.

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

notice how it only generates valid combinations by keeping track of how many more items are possible for each of the combinations. So, this wouldnt be brute force, and it would actually do the minimum work needed to generate the set of combinations.