大输入量动态编程 [英] Dynamic programming with large inputs

问题描述

我正在尝试解决一个容量为30.000.000的经典背包问题，它可以很好地工作到20.000.000，但随后内存不足：

I am trying to solve a classic Knapsack problem with huge capacity of 30.000.000 and it works well up until 20.000.000 but then it runs out of memory:

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

我试图进行除法所有值和容量都乘以1.000.000，但是会生成浮动值，我认为这不是正确的方法。我也尝试过使类型的数组和矩阵变长，但这无济于事。
也许是另一个数据结构？
欢迎使用任何指针...

I have tried to divide all values and capacity by 1.000.000 but that generates floats and I don't think that is the correct approach. I have also tried to make the arrays and matrix of type long but that does not help. Perhaps another data-structure? Any pointers welcome...

代码：

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

推荐答案

以下是我用于此类操作的一些技巧。

Here are a couple of tricks I've used for things like that that.

首先，是稀疏矩阵的一种变体。并不是稀疏，而是假设未存储的条目为零，而是假定它们与之前的条目相同。这可以在任一方向（沿装货方向或物品方向）上工作，而不能（轻易）同时在两个方向上工作。是个好把戏，但不会打败双向的巨大实例。

First, a variant of a sparse matrix. It's not really sparse, but instead of assuming that "non-stored entries" are zero, you assume they're the same as the entry before. This can work in either direction (in the direction of the capacity or in the direction of the items), afaik not (easily) in both directions at the same time. Good trick, but doesn't defeat instances that are huge in both directions.

第二，将动态编程和Branch&界。首先，仅将DP与最后两行一起使用。这为您提供了最佳解决方案的价值。然后使用Branch&绑定以找到与最佳解决方案相对应的项子集。按值/权重排序，应用松弛值 value [next_item] *（capacity_left / weight [next_item]）绑定用。

Secondly, a combination of Dynamic Programming and Branch & Bound. First, use DP with only the "last two rows". That gives you the value of the optimal solution. Then use Branch & Bound to find the subset of items that corresponds to the optimal solution. Sort by value/weight, apply the relaxation value[next_item] * (capacity_left / weight[next_item]) to bound with. Knowing the optimal value ahead of time makes pruning very effective.

最后两行是指上一行（包含解决方案的表格的一部分）直到 i ）和当前行（您正在填写）的所有项目。例如：（这是C＃btw，但应该易于移植）

The "last two rows" refers to the "previous row" (a slice of the tableau that has the solutions for all items up to i) and the "current row" (that you're filling right now). it could look something like this, for example: (this is C# btw, but should be easy to port)

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

这篇关于大输入量动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！