java - 优化递归回溯
问题描述
我通过回溯所有可能的解决方案解决了背包问题的一个变体。基本上 0 表示该物品不在背包中,1 表示该物品在背包中。成本是背包中所有物品的价值,我们试图在拥有每个“类别”物品的同时达到尽可能低的价值。每次找到所有类的组合时,我都会计算所有项目的值,如果它低于 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;
}
}
解决方案
- 请原谅我的直言不讳,但是您在优化低效算法方面的努力只能被描述为抛光粪便。您不会通过蛮力解决任何体面大小的背包问题,而且早期返回是不够的。我已经提到了一种在 CodeReview SE 上编写高效程序的方法;这需要相当大的努力,但你必须做你必须做的事情。
话虽如此,我建议您将其写入
arr
控制台以便对序列进行故障排除。看起来当您返回 indexi-1
时, at 的元素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
,您应该存储提供它的实际数据。但主要建议是:当您的算法表现异常时,跟踪是您的朋友。
推荐阅读
- c# - 重新加载模型时,不会在类中重新生成数据注释
- c++ - 找不到 windows.winmd – 如果指定了路径,则错误相乘
- ffmpeg - ffmpeg - 确定哪些参数
- mongodb - 如何使用 moongose 将结果限制在一个类别中
- c# - UWP VisualTreeHelper.GetParent() 返回 null
- android - 调用异步任务和 onPostExecute 后如何绘制地图?
- javascript - 如何从 2 个集合 nodejs 和 mongodb 中获取关系信息
- android - 比较图像中的两个对象
- php - 如何将会话变量的时间更长?
- android - 如何从 Google 语音助手访问我的 Android 应用程序