Hi, I got java.lang.OutOfMemoryError: Java heap space while trying to solve this Algorithm problem, what can be done?

Question

这个问题类似于子集和，我们确定一个数字列表是否有一个子集产生给定的总和，但在这种情况下，我们可以从列表 p 的元素创建一个子集仅当它等于或大于其他列表 q 中的相应元素时。同样，k 不是元素值的总和，而是可以添加的元素数。因此，如果 k 为 3，我们需要 select 列表 p 中的 3 个元素，但这些元素不能小于列表 q 中的相应元素。 我是动态规划和背包的新手，请帮助我。

public static List<Integer> kthPerson(int k, List<Integer> p, List<Integer> q) {

    List<Integer> q1 = new ArrayList<>();
    q1.addAll(q);
    Collections.sort(q1);

    int maxQ = q1.get(q1.size()-1);

    List<Integer> res = new ArrayList<>();

    int[][] dp = new int[k+1][maxQ+1];
    for(int[] d:dp){
        Arrays.fill(d, 0);
    }

    for (int u = 0; u < maxQ; u++) {
        int count = 0;
        for (int i = 0; i < p.size(); i++){
            if (p.get(i) >= u){
                dp[count][u] = i+1;
                count++;
            }
            if (count == k){
                break;
            }
        }
    }

    for (int s = 0; s < q.size(); s++) {
        res.add(dp[k-1][q.get(s)]);
    }
    return res;
}

/*if you want to test*/
public static void main(String args[]) {



        List<Integer> p = new ArrayList<>();

        p.add(1);
        p.add(4);
        p.add(4);
        p.add(3);
        p.add(1);
        p.add(2);
        p.add(6);

        List<Integer> q = new ArrayList<>();

        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        q.add(5);
        q.add(6);
        q.add(7);

        kthPerson(2, p, q);


    }
 /*you will get 
2
3
3
3
0
0
0. which is desired result but when the input is really large I get the java heap error*/

Answer 1

其实这道题不需要动态规划。没有一个案例实际上是基于它以前的案例。
因此你可以写这个函数：

public static List<Integer> kthPersonNew(int k, List<Integer> p, List<Integer> q) {
    List<Integer> res = new ArrayList<>();

    for (int limit : q) {
        int count = 0;
        boolean added = false;
//      For each person index
        for (int i = 0; i < p.size(); i++) {
//          If this person is higher than the needed limit - count it
            if (p.get(i) >= limit) {
                count++;
//              If you have counted k persons than add the kth person to res and break
                if (count == k) {
                    res.add(i + 1);
                    added = true;
                    break;
                }
            }
        }
//      In case no one was added than add 0
        if (!added) {
            res.add(0);
        }
    }
    return res;

}

它为您提供的测试用例提供相同的输出。

p = [1, 4, 4, 3, 1, 2, 6]
q = [1, 2, 3, 4, 5, 6, 7]
=>
res = [2, 3, 3, 3, 0, 0, 0]

现在我确定该程序不会导致 java.lang.OutOfMemoryError，因为您只使用一个数组并且它的长度与 q 相同。
这应该可以解决您的问题。

编辑：
看起来新算法在内存方面很好但不够快，假设 q 总是在增长，我们可以使用它并确保时间复杂度总是小于 O(q * k + n)。由于每个不适合当前限制的元素将不适合未来的限制。

我们需要一个帮手 class:

class Element{
    private int index;
    private int value;

    public Element(int index, int value){
        this.index = index;
        this.value = value;
    }

    public int getIndex(){
        return this.index;
    }

    public int getValue(){
        return this.value;
    }

    @Override
    public String toString(){
        return value + " " + index;
    }

    public void print(){
        System.out.println(this);
    }
}

这样即使删除后我们也能记住旧的变量索引。

以及新函数：

public static List<Integer> kthPersonFast(int k, List<Integer> p, List<Integer> q) {
    List<Integer> res = new ArrayList<>();

    List<Element> elements = new LinkedList<Element>();
    for (int i = 0; i < p.size(); i++) {
        elements.add(new Element(i, p.get(i)));
    }

    for (int limit : q) {
        int count = 0;
        boolean added = false;
//          For each person         
        Iterator<Element> itr = elements.iterator(); 
        while (itr.hasNext()) { 
            Element person = itr.next(); 

//              If this person is higher than the needed limit - count it
            if (person.getValue() >= limit) {
                count++;
//                  If you have counted k persons than add the kth person to res and break
                if (count == k) {
                    res.add(person.getIndex() + 1);
                    added = true;
                    break;
                }
            } else {
//                  If the person didn't fit for that limit it will not fit to any other limit
//                  since we are assuming the limits are always growing
                itr.remove();
            }
        }
//          In case no one was added than add 0
        if (!added) {
            res.add(0);
        }
    }
    return res;
}

您还需要导入：

import java.util.Iterator;
import java.util.LinkedList;

应该是这样。

祝你好运

Answer 2

您可能需要查看程序的其他部分，看看是否可以删除未使用的对象。在这种情况下，我们需要查看更多代码。话虽这么说，如果您还没有尝试过，您可能会从以下内容中受益：

如果您使用的是 64 位 JVM，则只需增加堆大小即可。

java -Xmx4G -jar MyProgram.jar

https://javarevisited.blogspot.com/2011/05/java-heap-space-memory-size-jvm.html

Hi, I got java.lang.OutOfMemoryError: Java heap space while trying to solve this Algorithm problem, what can be done?

Hi, I got java.lang.OutOfMemoryError: Java heap space while trying to solve this Algorithm problem, what can be done?

java

algorithm

knapsack-problem