5

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

1 ответ 1

6

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.