задача о ранце на С# методом динамического программирования

[Fiamma]

Доброго времени суток.

Собственно, решение самой задачи о ранце пока не интересует, а интересует создание бинарного дерева вида:


Есть зачатки кода, но они как-то пока не работают:
Класс tree:

class tree  //класс бинарного дерева
    {
         public struct item //структура предмета
         {
            public double weight; //вес
            public double value;  //ценность
         }
         public item []items;  //массив предметов

         public int index;     //индекс уровня узла предмета в дереве
         public double weight;  //вес 
         public double value;   //ценность
         public tree left;      //левая ветвь дерева (предмет не взят)
         public tree right;     //правая ветвь дерева (предмет взят)
         //метод добавления узла к дереву
         public void insert(tree elem, int index, double weight, double value)
         {
            if (elem.left == null && elem.right == null) //если текущий узел пуст, он не имеет ветвей
            {
                elem.index = index; //заполняем значения
                elem.weight = weight;
                elem.value = value;
                elem.left = new tree();  //инициализируем ветви
                elem.right = new tree();
            }
            else  //если текущий узел не пуст
            {
                if (elem.weight ==weight && elem.value == value) //условие перехода по левой ветви
                elem.left.insert(elem.left, index, weight, value); 
                else if (elem.weight.CompareTo(weight) != 0) //условие перехода по правой ветви
                elem.right.insert(elem.right, index, elem.weight + weight, value);
            }
        }
    }

Создание дерева:

 private void button2_Click(object sender, EventArgs e)
        {
            tree graf = new tree(); //создание объекта класса "дерево"
            graf.items = new tree.item[n+1]; //создание списка предметов
            graf.items[0].weight = 0; //для правильного функционирования нужен
            graf.items[0].value = 0;  //нулевой предмет - корень дерева
            for (int i = 1; i < n + 1; i++) //добавление предметов в список
            {
                graf.items[i].weight = System.Convert.ToDouble(this.dataGridView1[1, i].Value);
                graf.items[i].value = System.Convert.ToDouble(this.dataGridView1[2, i].Value);
            }

            for (int i = 0; i < n + 1; i++)
            {
                int count = 0;
                tree t = new tree();
                t.index = i;
                t.weight = graf.items[i].weight;
                t.value = graf.items[i].value;
                graf.insert(graf, t.index, t.weight, t.value);
                count = i + 1;
                while (count < n + 1)
                {
                    t.index = count;
                    graf.insert(graf, t.index, t.weight, t.value);
                    count++;
                }
            }
        }

Собственно, правильно создаются все левые ветви и самая правая. Правые ветви от "левых" узлов не заполняются и я не могу придумать, как туда попасть. Помогите, пожалуйста.

[Базиля]

А можно дерево представить в более свойственном ему виде?

[Fiamma]

В каком-таком более свойственном?

Наверное, можно, если при этом оно останется деревом, пригодным для решения данной задачи) Суть в том, чтобы потом пропустить это дерево через сеть Хопфилда, которая должна найти путь максимальной длинны, т.е., собственно, решение задачи. Такая вот курсовая работа.

[Базиля]

В каком-таком более свойственном?

А как по Вашему представляют дерево в графическом виде?
Можете просто нарисовать его в более "читабельной" форме и выложить сюда рисунок?

[Fiamma]

Эмм... Так нагляднее?)
pic
Ветви, окрашенные красным, не удается создать.

[Базиля]

Хорошо, я сейчас убегаю просто, ближе к вечеру гляну.
Если никто другой не отзовется, я отпишусь

[Базиля]

Посмотрел.

Правые ветви от "левых" узлов не заполняются и я не могу придумать, как туда попасть. Помогите, пожалуйста.

Что значит:

и я не могу придумать, как туда попасть

Тут ничего придумывать не нужно, каждый новый элемент, при добавлении, встает на свое законное место и никак иначе
Я думаю Вам объяснять не нужно, по какому принципу заполняются деревья бинарного поиска.
У Вас же этот принцип заполнения по каким-то основаниям нарушен, хотелось бы узнать что послужило причиной этому?

Можно еще пример самих входных данных?

[NomenEstOmen]

Вообще, задача интересная. Я даже пытался делать её на С. Правда, я просто строил матрицу N*(Cap+1), где Cap - это ёмкость рюкзака, а N - количество элементов. И на i-м (0<=i<N) шаге для каждого j (0<=j<=Cap) просто смотрел, можно ли добавить при такой (j) ёмкости очередной (i-й) элемент, не ухудшая набор. Если всю эту матрицу сохранить, то обратным ходом можно будет выяснить, какие элементы в оптимальный набор войдут, а какие - нет. Я даже скомпилил прогу, которая берет задачу в виде файла и в другой файл записывает решение. Может, пригодится...