java - 大输入动态规划

Question

我正在尝试解决一个容量为 30.000.000 的经典背包问题，它在 20.000.000 之前运行良好，但随后内存不足:

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

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

代码:

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


    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

这里有一些我在类似的事情上使用过的技巧。

首先，稀疏矩阵的变体。它并不是真正稀疏，而是假设“非存储条目”为零，而是假设它们与之前的条目相同。这可以在任一方向上起作用(在容量方向上或在元素方向上)，据我所知，不能(容易)同时在两个方向上起作用。好技巧，但无法击败双向巨大的实例。

其次，动态规划与分支定界法的结合。首先，仅对“最后两行”使用 DP。这为您提供了最佳解决方案的值(value)。然后使用分支限界来查找与最优解决方案相对应的项目子集。按值/重量排序，应用松弛value[next_item] * (capacity_left/Weight[next_item])进行绑定(bind)。提前知道最优值使得剪枝非常有效。

“最后两行”指的是“前一行”(表格的一部分，其中包含直到 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];