Java中的数组递归背包

Question

我读过很多关于背包问题的变体，但是我所负责的版本有点不同，我不太明白如何解决它

我有一个表示权重的整数数组（即{1,4,6,12,7,2}），只需要找到一个与目标权重相加的解

我理解基本算法，但我不知道如何实现它

首先，我的基本情况是什么？是在数组为空时吗？目标达到了吗？目标超额完成了吗？或者是某种组合

第二，当目标超额完成时，我如何回溯并尝试下一项

第三，我应该返回什么？我应该返回INT（在这种情况下，我应该打印出来吗？）？还是返回数组，最终返回的是解决方案

Answer 1

仔细考虑你要解决的问题。为了解决这个问题，我 考虑背包算法的输入和输出

输入：一组整数（背包）和一个整数（建议的总和）

输出：一组加起来等于建议总和的整数，或null

这样，您的代码可能如下所示

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

递归算法很简单。首先计算袋子的总和。如果它等于 prospectiveSum然后返回麻袋。否则，在sack上迭代，并为每个项目初始化一个新的背包，移除该项目。打电话给背包解决这个问题。如果有解决方案，请返回。否则继续下一项

例如，如果我们调用背包求解（{1,2,3}，5），算法尝试1+2+3=5，这是错误的。因此它通过{1,2,3}循环并调用子列表{2,3}、{1,3}和{1,2}上的背包求解。背包求解（{2,3}，5）是返回解的方法

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

Answer 2

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