更新:基于rrenaud的伟大评论,我想澄清的是,虽然我生成的所有排列顺序并不重要(所以它不完全像一个旅行推销员问题,但仍然有点相似)。我关注的重点是我的问题(尽管对如何加速这一问题的任何见解都是受欢迎的),结果是相互建立的,也许有方法(动态规划?),我可以用它来构建先前的结果而不是重复大量的计算。看看这些结果,你可以看到的结果都只是建立在彼此(这样做是为了项目的代码变更数量为3,在for循环中最多3个):算法是指数型的,有没有办法让它不是这样?
Grapes = 0
Strawberries = 0
Raspberries = 0
****
Grapes = 1
Strawberries = 0
Raspberries = 0
****
Grapes = 2
Strawberries = 0
Raspberries = 0
****
Grapes = 3
Strawberries = 0
Raspberries = 0
****
Grapes = 0
Strawberries = 1
Raspberries = 0
****
Grapes = 1
Strawberries = 1
Raspberries = 0
****
Grapes = 2
Strawberries = 1
Raspberries = 0
****
Grapes = 3
Strawberries = 1
Raspberries = 0
****
Grapes = 0
Strawberries = 2
Raspberries = 0
****
Grapes = 1
Strawberries = 2
Raspberries = 0
****
Grapes = 2
Strawberries = 2
Raspberries = 0
****
Grapes = 3
Strawberries = 2
Raspberries = 0
****
Grapes = 0
Strawberries = 3
Raspberries = 0
****
Grapes = 1
Strawberries = 3
Raspberries = 0
****
Grapes = 2
Strawberries = 3
Raspberries = 0
****
Grapes = 3
Strawberries = 3
Raspberries = 0
****
Grapes = 0
Strawberries = 0
Raspberries = 1
****
Grapes = 1
Strawberries = 0
Raspberries = 1
****
Grapes = 2
Strawberries = 0
Raspberries = 1
****
Grapes = 3
Strawberries = 0
Raspberries = 1
****
Grapes = 0
Strawberries = 1
Raspberries = 1
****
Grapes = 1
Strawberries = 1
Raspberries = 1
****
Grapes = 2
Strawberries = 1
Raspberries = 1
****
Grapes = 3
Strawberries = 1
Raspberries = 1
****
Grapes = 0
Strawberries = 2
Raspberries = 1
****
Grapes = 1
Strawberries = 2
Raspberries = 1
****
Grapes = 2
Strawberries = 2
Raspberries = 1
****
Grapes = 3
Strawberries = 2
Raspberries = 1
****
Grapes = 0
Strawberries = 3
Raspberries = 1
****
Grapes = 1
Strawberries = 3
Raspberries = 1
****
Grapes = 2
Strawberries = 3
Raspberries = 1
****
Grapes = 3
Strawberries = 3
Raspberries = 1
****
Grapes = 0
Strawberries = 0
Raspberries = 2
****
Grapes = 1
Strawberries = 0
Raspberries = 2
****
Grapes = 2
Strawberries = 0
Raspberries = 2
****
Grapes = 3
Strawberries = 0
Raspberries = 2
****
Grapes = 0
Strawberries = 1
Raspberries = 2
****
Grapes = 1
Strawberries = 1
Raspberries = 2
****
Grapes = 2
Strawberries = 1
Raspberries = 2
****
Grapes = 3
Strawberries = 1
Raspberries = 2
****
Grapes = 0
Strawberries = 2
Raspberries = 2
****
Grapes = 1
Strawberries = 2
Raspberries = 2
****
Grapes = 2
Strawberries = 2
Raspberries = 2
****
Grapes = 3
Strawberries = 2
Raspberries = 2
****
Grapes = 0
Strawberries = 3
Raspberries = 2
****
Grapes = 1
Strawberries = 3
Raspberries = 2
****
Grapes = 2
Strawberries = 3
Raspberries = 2
****
Grapes = 3
Strawberries = 3
Raspberries = 2
****
Grapes = 0
Strawberries = 0
Raspberries = 3
****
Grapes = 1
Strawberries = 0
Raspberries = 3
****
Grapes = 2
Strawberries = 0
Raspberries = 3
****
Grapes = 3
Strawberries = 0
Raspberries = 3
****
Grapes = 0
Strawberries = 1
Raspberries = 3
****
Grapes = 1
Strawberries = 1
Raspberries = 3
****
Grapes = 2
Strawberries = 1
Raspberries = 3
****
Grapes = 3
Strawberries = 1
Raspberries = 3
****
Grapes = 0
Strawberries = 2
Raspberries = 3
****
Grapes = 1
Strawberries = 2
Raspberries = 3
****
Grapes = 2
Strawberries = 2
Raspberries = 3
****
Grapes = 3
Strawberries = 2
Raspberries = 3
****
Grapes = 0
Strawberries = 3
Raspberries = 3
****
Grapes = 1
Strawberries = 3
Raspberries = 3
****
Grapes = 2
Strawberries = 3
Raspberries = 3
****
Grapes = 3
Strawberries = 3
Raspberries = 3
****
我还在学习算法,所以我的知识库有点有限。我基本上有一个递增,随着我增加更多的输入,它会以指数形式增长,但我想知道是否有任何我可以用来使它不这样做。
下面是一个递归示例(java代码),它基本上是一个项目列表,并使用0-n个数字计算出每个项目的所有组合(为了简单起见,我的代码有2个项目,每个项目的数量为0到5 ...变量可以在循环中更改)。为了使这更有趣,我有一个名为Q的变量,它执行一些随机处理,并根据列表检查其值,然后才继续。我评论的代码,以及我能,所以希望它很容易为你读:
import java.util.Arrays;
import java.util.List;
//learning playground safe to delete
public class main {
public static void main(String[] args) {
System.out.println("Starting..");
Integer number_of_items = 2; //how many items should we test with, over 7 or 8 takes a long time MAX is 11(based on the number of names we have below)
long startTime = System.currentTimeMillis(); //start timer
Integer[] integers_temp = new Integer[number_of_items]; // create a list with exactly the number of items specified above
Arrays.fill(integers_temp, 0); // populate list with zeros
List<Integer> list_to_start = Arrays.asList(integers_temp); //set it as a list
String[] name_of_list_to_start = new String[] {"Grapes", "Strawberries", "Raspberries", "Blackberries", "Pineapples", "Oranges", "Prunes", "Pears", "cherries", "Peaches", "Apples"};
List<Integer> numbers_to_choose_from = Arrays.asList(new Integer[] {0, 1,2,3,4,5,6,7,8,9,10}); //list of numbers program can choose from(could be anything,just learning)
counter(list_to_start.size(), list_to_start, name_of_list_to_start, numbers_to_choose_from);
long endTime = System.currentTimeMillis();
System.out.println("Total execution time: " + (endTime-startTime));
}
private static void counter(int length, List<Integer> list_to_start, String[] name_of_list_to_start, List<Integer> numbers_to_choose_from) {
// If we've gone through everything then return the results
if (length == 0) {
for (int i = 0; i<list_to_start.size(); i++) {
System.out.println(name_of_list_to_start[i] + " = " + list_to_start.get(i));
}
System.out.println("****");
return;
}
//This part basically increments list_to_start and then the above part displays it.
for (int i = 0; i<=5; i++) {
int q = i +2; //do anything here..random just for example, right now just takes the number in the loop and adds by 10
//System.out.println(q); // this area is looped as many times as i^items, yet seems like after the first run work is duplicated.
if (length != 0 && numbers_to_choose_from.contains(q)) {
list_to_start.set((length-1), q);
counter((length-1), list_to_start, name_of_list_to_start, numbers_to_choose_from);
list_to_start.set((length-1), 0);
}
}
}
}
如果更改了批量0-10和项目10则变成(10^10这是百亿循环) 。当我剖析代码时,它说大部分时间都花在迭代器上,这是有道理的,所以我需要以某种方式减少迭代花费的时间(希望有一种方法可以让它在每个项目上迭代一次,而不是在每次递归上) 。
我的观察是循环似乎是必要的,因为它计算并检查列表中的值,但是一旦循环完成,所有其他时间都重复相同的过程。我对所有的算法都很陌生(但目前正在阅读算法的介绍),所以我想知道是否有办法让这个不是指数的,所以它可以处理更多的变量(这是我的程序的一部分, ,但理想情况下,我需要尽可能多的处理,但至少有0-100个数量的100个项目,并在一小时内完成,否则其他工作将失败。我无法通过100^100达到这个目标,所以我挣扎着想法)。
如果任何人有任何提示,或者他们看到任何算法解决类似的问题,这将是伟大的,因为我可以研究他们使用的逻辑,看看它是否适用。如果有人有直接的解决方案,那么这太棒了!
我希望这个问题不是太长,是有道理的(我试图尽可能详细)
你想要你的代码做什么?你想解决什么问题? – 2012-04-06 18:46:11
这是一些制造问题,我并不是很感兴趣详细了解它究竟做了什么或应该做什么,但从粗略的一瞥看,它似乎[knapsacky](http://en.wikipedia.org/wiki/) Knapsack_problem) - 这意味着它是NP-hard,但是存在伪多项式动态编程算法 – Voo 2012-04-06 18:46:14
是否非常有效的算法取决于项目如何组合以及您想要的组合之外的内容。例如,如果项目是城市,并且您通过在城市之间旅行来组合它们,则如果您想要在两个给定城市之间建立最短路径,那么您将拥有一条快速最短路径算法。另一方面,如果你想要访问它们的最短路径,你会遇到一个难以驾驭的推销员问题。 – 2012-04-06 20:36:58