Задача о ранце. Как сократить память? - 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];
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д