java - Java 递归回溯

Question

我学习计算机科学，目前正在练习回溯，因为我非常不擅长它。我在网上找到了这个练习：

你在卖苹果。这是您的苹果的当前价格表：

数量 1 2 3 4 5 6 7 8 价格 1 5 8 9 10 17 17 20

因此，如果您一次销售 8 个苹果，您将获得 20 美元。如果您先卖 6，然后再卖 2，您将获得 22 美元。尝试找到最大的利润。这是方法，您应该使用：

public static long sellApples(int count, long[] prices) {

}

现在我想了 5 个小时，但我无法找到一个好的解决方案。有人来挑战一下吗？

标签： javarecursive-backtracking

Answer 1

我不是这方面的专家，所以我对我说的话持保留态度。

在该方法中，您需要将计数拆分为多个部分，例如8 => 3, 5. 您需要再次调用此方法，这两个值都为count. 这是更明显的部分。

棘手的部分是您需要承认将计数分成 2 部分就足够了。我的意思是您不需要尝试使用1,2,5值调用该方法，因为如果您只是使用 调用它3,5，那么下一次迭代可以拆分3为1,2.

更明显的事实是，如果您尝试过，3,5则无需尝试5,3。

因此，如果您的输入是 8，那么您尝试8, 1,7, 2,6,并比较结果3,5，4,4选择最大的一个。从您提供的方法存根中，我假设您不需要返回如何获得该结果，只需返回最大结果本身