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

#c_sharp #алгоритм #оптимизация #память

Получил задание решить классическую задачу о ранце. Есть 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];
        }
    }
}

    

Ответы

Ответ 1

При заполнении матрицы 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];
}


Именно так и выглядит классический алгоритм рюкзака.