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

@DigitalGod · Регистрация: 11.12.2014

Author24 — интернет-сервис помощи студентам

Доброго времени суток! Получил задание решить классическую задачу о ранце. Есть N предметов, у каждого предмета есть вес и цена, есть ранец, который выдерживает определённый вес. Задача унести как можно больше в денежном эквиваленте(вывести максимальную сумму денег). Задачу я решил, но в одном из 10 тестов на специальном сайте я получил "ошибку" Out of memory, что означает, что нужно как-то уменьшить колл-во памяти. Как я понял я могу использовать то, что мне не нужен список предметов, только суммарный вес, но как это реализовать я не знаю. Вот мой код, жду идеи, предложения

C#

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];
        }
    }
}

@Sanek32 · 17.05.2017, 05:57

C#

1	static long bag(ref long[] vaha,ref long[] ceny,ref long _max)

@Storm23 · 17.05.2017, 08:26

DigitalGod,
Во-первых, зачем вам long? Может обойтись int?
Во-вторых, судя по вашему алгоритму, вы в цикле обращаетесь только к предыдущей строке массива pl (то есть к pl[i, j - 1]). Соотв, зачем вам хранить все предыдущие значения pl? Храните только последнюю строку:

C#

        static long bag(long[] vaha, long[] ceny, long _max)
        {
            long n = vaha.Length;
            long[] pl = new long[_max + 1];
            long[] prev_pl = new long[_max + 1];
            for (int j = 1; j <= n; j++)
            {
                for (int i = 1; i <= _max; i++)
                {
                    if (vaha[j - 1] <= i)
                    {
                        pl[i] = Math.Max(prev_pl[i], prev_pl[i - vaha[j - 1]] + ceny[j - 1]);
                    }
                    else
                    {
                        pl[i] = prev_pl[i];
                    }
                }
                //swap
                var temp = pl;
                pl = prev_pl;
                prev_pl = temp;
            }
            return pl[_max];
        }

Sanek32, массив - ссылочный тип. При передаче в метод, копия массива не делается. Соотв и делать ref смысла нет.

@DigitalGod · 17.05.2017, 13:06 **[ТС]**

Storm23, long нужен был по условию.

Добавлено через 14 минут
Storm23, то, что вы написали показалось мне логичным, но оно не работает

На вот такой ввод программа выдаёт ответ 12, а должна 20
6
3
3 5
2 7
3 13

@Storm23 · 17.05.2017, 14:22

Сообщение от DigitalGod

то, что вы написали показалось мне логичным, но оно не работает
На вот такой ввод программа выдаёт ответ 12, а должна 20

Там просто в последней строке нужно возвращать не pl, а prev_pl:

C#

1	return prev_pl[_max];

@DigitalGod 4 / 4 / 1 Регистрация: 11.12.2014 Сообщений: 26
	17.05.2017, 13:06 [ТС]	4
	Storm23, long нужен был по условию. Добавлено через 14 минут Storm23, то, что вы написали показалось мне логичным, но оно не работает На вот такой ввод программа выдаёт ответ 12, а должна 20 6 3 3 5 2 7 3 13 0

	17.05.2017, 14:22

Опции темы

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

Решение