Java中的递归背包

我已经阅读了很多背包问题的变体，但我负责的版本有点不同，我不太明白如何解决它。Java中的递归背包

我有一个代表权重的整数数组（即{1,4,6,12,7,2}），并且只需要找到一个合计目标权重的解决方案。

我明白基本的算法，但我不明白如何实现它。

首先，我的基本情况是什么？数组是否为空？目标已经达到？目标已经超过了？或者也许有一些组合？

其次，当目标超出时，我该如何回溯并尝试下一个项目？

三，我应该返回什么？我应该回国吗（在这种情况下，我应该把它们打印出来吗？）？或者我返回数组，最终的回报是解决方案吗？

来源

2014-10-29 SFBA26

仔细想想你正试图解决的问题。为了解决这个问题，我是考虑了Knapsack算法的输入和输出。

输入：一个整数集（背包）和一个整数（所提出的总和）

输出：一套谁加起来之和建议，或空整数。

这样，您的代码可能看起来像这样

public int[] knapsackSolve(int[] sack, int prospectiveSum) { 
    //your algorithm here 
}

递归算法很简单。首先计算麻袋的总和。如果它等于 prospectiveSum然后返回袋。否则，遍历麻袋，并为每个项目初始化一个新的背包与该项目删除。在这里调用knapsackSolve。如果有解决方案，请将其退回。否则，进入下一个项目。

例如，如果我们调用knapsackSolve（{1,2,3}，5），算法会尝试1 + 2 + 3 = 5这是错误的。因此它循环遍历{1,2,3}并在子列表{2,3}，{1,3}和{1,2}上调用knapsackSolve。 knapsackSolve（{2,3}，5）是返回解决方案的一个。

这不是一个非常有效的算法，虽然它很好地说明了背包问题有多复杂！

来源

2014-10-29 08:01:21 YardGlassOfCode

你说输出是一组**整数，但我只在你的示例代码中看到“int” – 2014-10-29 12:38:25

就问题而言，输出是一组整数。在解决方案（实现）方面，输出是'int []'。所以我并不是指'Set '意义上的一组整数。这个解决方案使用'Set '是一个好主意，但我认为数组会更简单。 – YardGlassOfCode 2014-10-29 20:24:37

基本上将背包问题表述为（从Wikipedia）：“给定一组项目，每个项目都有一个质量和一个值，确定要包含在一个集合中的每个项目的数量，以便总重量小于或者等于一个给定的限制，并且总的值是尽可能大的，对于你的问题，我们只对权重感兴趣，所以你可以将所有的值都设置为1.此外，我们只想知道目标权重是否可以准确达到。我猜你可以只使用一次而不是多次使用重量？这个问题可以用动态编程很好地解决。你是否熟悉这个原理？应用动态编程比编程回溯更加优雅和快速。您只能使用上面发布的user2738608的方法进行回溯。

来源

2014-10-29 12:33:54 BluesSolo

Java中的递归背包

回答

相关问题