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

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток! Получил задание решить классическую задачу о ранце. Есть N предметов, у каждого предмета есть вес и цена, есть ранец, который выдерживает определённый вес. Задача унести как можно больше в денежном эквиваленте(вывести максимальную сумму денег). Задачу я решил, но в одном из 10 тестов на специальном сайте я получил "ошибку" Out of memory, что означает, что нужно как-то уменьшить колл-во памяти. Как я понял я могу использовать то, что мне не нужен список предметов, только суммарный вес, но как это реализовать я не знаю. Вот мой код, жду идеи, предложения
п»їusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using CodEx;
 
namespace ConsoleApplication17
{
    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];
        }
    }
}

Решение задачи: «Задача о ранце. Как сократить память?»

textual
Листинг программы
return prev_pl[_max];

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4.154 из 5
Похожие ответы