Получил задание решить классическую задачу о ранце. Есть 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];
}
Именно так и выглядит классический алгоритм рюкзака.
Комментариев нет:
Отправить комментарий