Попытка заставить проблему рюкзака работать без многомерных массивов - PullRequest
Новая
       75

Попытка заставить проблему рюкзака работать без многомерных массивов

1 голос
/ 22 сентября 2019

Я пытаюсь сделать свою собственную реализацию алгоритма рюкзака, и мне было интересно, можно ли это сделать без многомерных массивов, что я чаще всего вижу в Интернете.

Идея заключалась не в том, чтобы создать самый оптимальный вариант, поэтому я просто использовал методы, которые, как мне казалось, могли сделать работу.(используя списки вместо int [])

Я чувствую, что близок к получению, но пока не совсем, и я не уверен, что делаю неправильно.

Ниже приводится функция драйвера, которая анализирует, скажем, следующий вход (вес: значение):

Макс

50

10: 60,20: 100,30: 120

Должно быть напечатано 220 и подмножество, его создающее.

CheckSum возвращает true, если значение при добавлении меньше или равно максимальному весу.

Хотя половина кода просто получает и помещает значения ... 

 public static bool Knapsack(int W, Dictionary<int, Tuple<int,int>> Items, List<int> numbers)
    {
        List<int> summationValue;
        List<int> subset;
        List<int> summationWeight;
        List<KeyValuePair<int, List<int>>> finalSet = new List<KeyValuePair<int, List<int>>>();

        for (int auto = 0; auto <= Items.Count-1; auto++)
        {
            Console.WriteLine("Iteration: " + auto);
            int value1 = Items[auto].Item2;
            int weight1 = Items[auto].Item1;
            summationValue = new List<int> { value1 };
            subset = new List<int> { (auto+1) };
            summationWeight = new List<int> { weight1 };
            //Initialize//var currentItem = itemIndex == 0 ? null : items[itemIndex - 1];
            for (int other_nodes = 0; other_nodes <= Items.Count-1; other_nodes++)
            {
                if (other_nodes == auto)
                {
                    other_nodes++;
                }
                int value2 = Items[other_nodes].Item2;
                int weight2 = Items[other_nodes].Item1;
                if (CheckSum(summationWeight, weight2, W))
                {
                    summationValue.Add(value2); 
                    subset.Add(other_nodes+1);
                    summationWeight.Add(weight2);
                    KeyValuePair<int, List<int>> kv = new KeyValuePair<int, List<int>>(summationValue.Sum(), subset);
                    finalSet.Add(kv);
                    break;
                }



            }

            //After all item iteration, print outputs; [Highest value] [Subset] [Weight]
            string printValue = summationValue.Sum().ToString();
            subset.Sort();
            string printWeight = summationWeight.Sum().ToString();

            Console.WriteLine("Highest Value: ");
            Console.WriteLine(printValue);
            Console.WriteLine("Subsets: \n");
            Console.Write("{ ");
            foreach (var i in subset)
            {
                 Console.Write(i + " ");
            }
            Console.WriteLine("}");
            Console.WriteLine("Highest Weight: ");
            Console.WriteLine(printWeight);
        }
        Console.WriteLine("[========================]");
        var pair = finalSet.OrderByDescending(x => x.Key).First();
        var keys = finalSet.Where(kvp => kvp.Key == pair.Key).Select(kvp => kvp.Key).ToArray();
        var fkey = keys.Max();
        Console.WriteLine(fkey);
        Console.Write("{ ");
        foreach (var i in pair.Value)
        {
            Console.Write(i + " ");
        }
        Console.Write("}");
        return true;
    }

Не включена функция linq для получения наибольшего ключа в списке, который соответствует наибольшему значению, что-то вроде: 

 finalSet.OrderByDescending(x => x.Key).First();

Я знаю, что это не лучший способ сделать это, но я все же хотел бы спросить, что я делаю неправильно в реализации.

В настоящее время этонапечатал бы для окончательного набора: 180, 1 3. Когда это должно было быть 220.

...