大输入动态规划

Question

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

我试图将所有的值和容量除以1.000.000，但这会产生浮点，我认为这不是正确的方法。我也试图使数组和矩阵的类型长，但这没有帮助。也许是另一种数据结构？欢迎任何建议...

代码：

public class Knapsack {
    public static void main(String[] args) {
         int N = Integer.parseInt(args[0]);   // number of items
         int W = Integer.parseInt(args[1]);   // maximum weight of knapsack
                

Answer 1

这里有几个我用过的技巧。

首先，一个稀疏矩阵的变体。它并不是真的稀疏，但不是假设“非存储条目”为零，而是假设它们与之前的条目相同。这可以在任何一个方向上工作（在容量的方向上或在项目的方向上），afaik不（容易）在两个方向上同时进行。很好的技巧，但不能击败双方都很大的例子。

其次，将动态规划与分枝定界相结合。首先，只使用“最后两行”的DP。这就给出了最优解的值。然后用分支定界法找到与最优解对应的项目子集。按值/weight排序，将松弛值[next_item]*(capacity_left/weight[next_item])应用到绑定。提前知道最优值使修剪非常有效。

int[] row0 = new int[capacity + 1], row1 = new int[capacity + 1];
for (int i = 0; i < weights.Length; i++)
{
    for (int j = 0; j < row1.Length; j++)
    {
        int value_without_this_item = row1[j];
        if (j >= weights[i])
            row0[j] = Math.Max(value_without_this_item,
                               row1[j - weights[i]] + values[i]);
        else
            row0[j] = value_without_this_item;
    }
    // swap rows
    int[] t = row1;
    row1 = row0;
    row0 = t;
}

int optimal_value = row1[capacity];