Оптимизация памяти алгоритма неограниченного рюкзака

В классическом решении алгоритма неограниченного рюкзака с использованием динамического программирования (https://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem) мы выделяем целочисленный массив размера рюкзака для хранения максимальных значений.Оптимизация памяти алгоритма неограниченного рюкзака

Если у меня есть рюкзак размером 1 миллиард, как я могу оптимизировать решение DP, чтобы убедиться, что я могу разместить массив int[] knapsack? Потому что память, взятая Java для 1B размера knapsack = 10^9 * 4Bytes = 3.7GB памяти.

источник

2016-12-29 figaro

Связанный: http://stackoverflow.com/questions/20407221/dynamic-programming-with-large-inputs – jarmod

Речь не идет об оптимизации решения DP, это вопрос нахождения совершенно другого решения. –

Вместо того, чтобы решить эту проблему со всеми данными в памяти, вам придется разработать решение, которое использует дополнительную память, например, доступ к файлу или, возможно, настройку базы данных.

источник

2016-12-29 02:23:08

Невозможно выделить ГБ памяти в кучу Java. Проблема в том, что наибольший одиночный массив в Java ограничен 2 ГБ. Поэтому используйте различные вспомогательные классы BigArray в Интернете или используйте массив массивов или другие классы коллекций. –

@JochenBedersdorfer Вы уверены в пределе 2GB? Потому что я сделал новый int [1000000000], и это работает для меня с 8-кусочной кучей. – figaro

1,000,000,000 даже не 1 ГБ :) –

Оптимизация памяти алгоритма неограниченного рюкзака

ответ

Смежные вопросы