-1

У меня задача не такая как все задачи на рюкзак, я попытался решить но мой алгоритм не проходит тесты, может кто-нибудь подскажет в чем проблема

введите сюда описание изображения

введите сюда описание изображения

using System;
using System.IO;

namespace Testing
{
    struct Item
    {
        public byte weight;
        public byte kilometres;
        public bool isTake;
    }

    class Program
    {
        static void Main(string[] args)
        {
            string[] lines = File.ReadAllLines("input.txt");
            int maxWeight = Int32.Parse(lines[0]);
            byte numberOfFood = byte.Parse(lines[1]);
            Item[] foodArray = new Item[numberOfFood];
            Item item;

            for (int i = 1; i <= numberOfFood; i++)
            {
                item.weight = Byte.Parse(lines[i + 1].Split()[0]);
                item.kilometres = Byte.Parse(lines[i + 1].Split()[1]);
                item.isTake = false;
                foodArray[i - 1] = item;
            }

            byte numberOfDrink = byte.Parse(lines[foodArray.Length + 2]);
            Item[] drinkArray = new Item[numberOfDrink];

            for (int i = 1; i <= numberOfDrink; i++)
            {
                item.weight = Byte.Parse(lines[i + foodArray.Length + 2].Split()[0]);
                item.kilometres = Byte.Parse(lines[i + foodArray.Length + 2].Split()[1]);
                item.isTake = false;
                drinkArray[i - 1] = item;
            }

            int weight;
            int[,,] func = new int[maxWeight + 1, numberOfFood, numberOfDrink];

            for (weight = 1; weight <= maxWeight; weight++)
            {

                for (int i = 1; i < foodArray.Length; i++)
                {

                    for (int j = 1; j < drinkArray.Length; j++)
                    {
                        if (foodArray[i].weight + drinkArray[j].weight > weight)
                        {
                            func[weight, i, j] = func[weight, i - 1, j - 1];
                            foodArray[i].isTake = false;
                            drinkArray[j].isTake = false;
                        }
                        else if (func[weight, i - 1, j - 1] >=
                                 (func[weight - drinkArray[j].weight - foodArray[i].weight, i - 1, j - 1] +
                                  foodArray[i].kilometres + drinkArray[j].kilometres))
                        {
                            func[weight, i, j] = func[weight, i - 1, j - 1];
                            foodArray[i].isTake = false;
                            drinkArray[j].isTake = false;
                        }
                        else
                        {
                            func[weight, i, j] = func[weight - drinkArray[j].weight - foodArray[i].weight, i - 1, j - 1] +
                                              foodArray[i].kilometres + drinkArray[j].kilometres;
                            foodArray[i].isTake = true;
                            drinkArray[j].isTake = true;
                        }
                    }
                }
            }

            int targetKilometres = 0;

            foreach (var drink in drinkArray)
            {
                if (drink.isTake)
                    targetKilometres = drink.kilometres;
            }

            foreach (var food in foodArray)
            {
                if (food.isTake)
                {
                    if(food.kilometres > targetKilometres)
                        targetKilometres = food.kilometres;
                }
            }

            Console.WriteLine(targetKilometres);
        }
    }
}
8
  • А описывать алгоритм кто будет? Словами... и подробно. Чтобы не гадать, что ты хотел сказать вот этой строкой кода.
    – Akina
    25 дек 2019 в 18:17
  • Проблема в том, что алгоритм как минимум неэффективен. Перебирать все веса в цикле не пойдёт. Надо бинарный или тернарный поиск.
    – Qwertiy
    25 дек 2019 в 18:19
  • @Akina, почему это не задача о рюкзаке? Вроде именно она.
    – Qwertiy
    25 дек 2019 в 18:20
  • 3
    @Akina Емкость 7, веса/питательность (3/10),(4/12),(5/21). Указанный метод даст вес 5 с расстоянием 21 км, а можно сделать 22 км
    – MBo
    25 дек 2019 в 18:34
  • @Akina, ну и с чего это должно работать?
    – Qwertiy
    25 дек 2019 в 19:06

1 ответ 1

0

Возможный алгоритм решения задачи.

Берём, например, еду. Генерируем все сочетания отдельных кусков такие, что совокупный вес не превышает грузоподъёмность минус самое лёгкое питьё, и считаем вес и дистанцию. Накапливаем результат - если такой вес отсутствует, запоминаем, если есть, запоминаем только если дистанция больше. Итогом будет массив наборов такой, что любой набор меньшего веса не позволит пройти такую же дистанцию.

Затем берём питьё и зеркально повторяем.

Получив два набора, ищем такую пару (один набор еды + один набор питья), что суммарный вес не превышает грузоподъёмность, а минимальное из расстояний максимально.

Это и будет решение задачи.

2
  • уточню. Все сочетания не надо, используйте стандартную динамику. Достаточно знать для каждого веса сколько максимум расстояния он даст.
    – pavel
    26 дек 2019 в 7:10
  • @pavel Угу. Но я не рассматривал оптимизацию. Впрочем, генерация сочетаний с верхним порогом может быть не хуже по сложности, чем динамика - просто надо сортировать по весу предварительно.
    – Akina
    26 дек 2019 в 7:12

Ваш ответ

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

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