gpt4 book ai didi

java - 优化递归回溯

转载 作者:行者123 更新时间:2023-12-02 01:39:52 25 4
gpt4 key购买 nike

我通过回溯所有可能的解决方案解决了背包问题的变体。基本上0表示该元素不在背包中,1表示该元素在背包中。成本是背包中所有元素的值(value),我们试图在拥有每个“类别”元素的同时实现尽可能低的值(value)。每次找到所有类的组合时,我都会计算所有项目的值,如果它低于 globalBestValue,我会保存该值。我这样做的是verify()

现在我正在尝试优化我的递归回溯。我的想法是在生成数组时对其进行迭代,如果生成的数字的“成本”已经高于我当前的最佳值,则返回生成器,因此当前生成的组合不能是新的最佳值并且可以跳过。

但是,通过我的优化,我的回溯并没有生成所有值,它实际上跳过了我试图找到的“最佳”值。你能告诉我问题出在哪里吗?

private int globalBestValue = Integer.MAX_VALUE;
private int[] arr;

public KnapSack(int numberOfItems) {
arr = new int[numberOfItems];
}

private void generate(int fromIndex) {
int currentCost = 0; // my optimisation starts here
for (int i = 0; i < arr.length; i++) {
if (currentCost > globalBestValue) {
return;
}
if (arr[i] == 1) {
currentCost += allCosts.get(i);
}
} // ends here
if (fromIndex == arr.length) {
verify();
return;
}
for (int i = 0; i <= 1; i++) {
arr[fromIndex] = i;
generate(fromIndex + 1);
}
}

public void verify() {
// skipped the code verifying the arr if it's correct, it's long and not relevant
if (isCorrect == true && currentValue < globalBestValue) {
globalBestValue = currentValue;
}else{
return;
}
}

最佳答案

  1. 请原谅我的直言不讳,但你对低效算法的优化只能用抛光来形容。你无法通过蛮力解决任何像样大小的背包问题,而且提前返回是不够的。我已经提到了一种在 CodeReview SE 上编写高效程序的方法;这需要付出相当大的努力,但你必须做你必须做的事情。
  2. 话虽如此,我建议您将 arr 写入控制台,以便对序列进行故障排除。看起来,当您返回到索引 i-1 时,i 处的元素仍设置为 1,并且您估计的是上限而不是下限。以下更改可能有效:替换您的代码

    for (int i = 0; i <= 1; i++) {
    arr[fromIndex] = i;
    generate(fromIndex + 1);
    }

    arr[fromIndex] = 1;
    generate(fromIndex + 1);
    arr[fromIndex] = 0;
    generate(fromIndex + 1);

这将其变成一种贪婪算法:您实际上不是从 0000000 开始,而是从 1111111 开始。显然,当您存储 globalBestValue 时,您应该存储提供它的实际数据。但主要的建议是:当你的算法表现得很奇怪时,跟踪就是你的 friend 。

关于java - 优化递归回溯,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57494618/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com