较大输入动态规划(Dynamic programming with large inputs)

我试图解决一个经典的背包问题的30.000.000巨大的容量和它工作得很好，直到20.000.000但随后运行的内存：

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

我试图通过1000000-把所有的价值观和能力，但其产生漂浮，我不认为这是正确的做法。我也试图让阵列和类长的基质，但没有帮助。也许另一个数据结构？任何指针欢迎...

码：

  公共类背包{      公共静态无效的主要（字串[] args）{           INT N =的Integer.parseInt（参数[0]）;  // 东西的个数           INT W =的Integer.parseInt（参数[1]）;  //背包的最大重量 

    int[] profit = new int[N+1];     int[] weight = new int[N+1];      // generate random instance, items 1..N     for (int n = 1; n <= N; n++) {         profit[n] = (int) (Math.random() * 1000000);         weight[n] = (int) (Math.random() * W);     }      // opt[n][w] = max profit of packing items 1..n with weight limit w     // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n?     int[][] opt = new int[N+1][W+1];     boolean[][] sol = new boolean[N+1][W+1];      for (int n = 1; n <= N; n++) {         for (int w = 1; w <= W; w++) {              // don't take item n             int option1 = opt[n-1][w];              // take item n             int option2 = Integer.MIN_VALUE;             if (weight[n] <= w) option2 = profit[n] + opt[n-1][w-weight[n]];              // select better of two options             opt[n][w] = Math.max(option1, option2);             sol[n][w] = (option2 > option1);         }     }      // determine which items to take     boolean[] take = new boolean[N+1];     for (int n = N, w = W; n > 0; n--) {         if (sol[n][w]) { take[n] = true;  w = w - weight[n]; }         else           { take[n] = false;                    }     }      // print results     System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take");     for (int n = 1; n <= N; n++) {         System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]);     }     //Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne. Last updated: Wed Feb 9       //09:20:16 EST 2011. }

Answer 1:

这里有几个技巧，我用这样的事情这一点。

首先，稀疏矩阵的一个变种。这不是真的稀疏，但不是假设“非存储条目”均为零，你认为他们是和以前一样的条目。这可以在工作任一方向（在容量的方向上或在物品的方向），不AFAIK（容易）在同时两个方向上。好招，但不战胜即是在两个方向上巨大的情况下。

其次，动态规划和分支和绑定的组合。首先，使用DP只用了“最后两行”。这使你的最佳解决方案的价值。然后使用科及一定能找到对应的最佳解决方案项目的子集。排序value/weight ，松弛施加value[next_item] * (capacity_left / weight[next_item])与结合用。提前知道最优值的时间使得修剪非常有效。

“最后两行”指的是“上一行”（即对所有项目到解决方案的画面一片i ）和“当前行”（即您填写现在）。它可能是这个样子，例如：（这是C＃顺便说一句，但应该很容易端口）

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];