Страницы

Поиск по вопросам

среда, 14 ноября 2018 г.

Задача о ранце. Как сократить память?

Получил задание решить классическую задачу о ранце. Есть N предметов, у каждого предмета есть вес и цена, есть ранец, который выдерживает определённый вес. Задача унести как можно больше в денежном эквиваленте(вывести максимальную сумму денег). Задачу я решил, но в одном из 10 тестов на специальном сайте я получил "ошибку" Out of memory, что означает, что нужно как-то уменьшить количество памяти. Как я понял я могу использовать то, что мне не нужен список предметов, только суммарный вес, но как это реализовать я не знаю.
using System; using System.Collections.Generic; using System.Linq; using System.Text; using CodEx;
namespace ranec { class Program { static long max, count; static long[] vah; static long[] cen; static void Main(string[] args) { max = long.Parse(Console.ReadLine()); count = long.Parse(Console.ReadLine()); vah = new long[count]; cen = new long[count]; for (int i = 0; i < count; i++) { vah[i] = Reader.Console().Int(); cen[i] = Reader.Console().Int(); } long d = bag(vah, cen, max); Console.WriteLine(d); Console.ReadLine(); }
//вот сама процедура поиска, vaha - массив весов, ceny массив цен, _max - максимальный вес, который выдерживает рюкзак //вопрос в том, какая часть массива pl мне не нужна?
static long bag(long[] vaha, long[] ceny, long _max) { long n = vaha.Length; long[,] pl = new long[_max+1, n+1]; for (int j = 1; j <= n; j++) { for (int i = 1;i <= _max; i++) { if (vaha[j-1] <= i) { pl[i, j] = Math.Max(pl[i, j-1], pl[i-vaha[j-1], j-1] + ceny[j-1]); } else { pl[i, j] = pl[i, j-1]; } } } return pl[_max, n]; } } }


Ответ

При заполнении матрицы pl вы обращаетесь только к предыдущей строчке. Отсюда и первый вариант оптимизации - хранить в памяти только две строчки, а не всю матрицу целиком.
Но можно пойти дальше - хранить в памяти всего одну строчку, делая вычисления сразу в ней. Так можно делать по той причине, что при вычислении pl[i,j] не бывает обращений к элементам с большими индексами - а потому если вычислять справа-налево, то дополнительная память для хранения "старых" значений никогда не понадобится. Просто уберите из своего алгоритма второй индекс у массива и разверните внутренний цикл в обратную сторону.
Тело цикла будет выглядеть примерно вот так (ветку else я выкинул из-за ее тривиальности):
if (vaha[j-1] <= i) { pl[i] = Math.Max(pl[i], pl[i-vaha[j-1]] + ceny[j-1]); }
Или, после дальнейших упрощений,
if (vaha[j-1] <= i && pl[i] < pl[i-vaha[j-1]] + ceny[j-1]) { pl[i] = pl[i-vaha[j-1]] + ceny[j-1]; }
Именно так и выглядит классический алгоритм рюкзака.

Комментариев нет:

Отправить комментарий