Советы, трюки и секреты для Blogger.com блоггеров. Все для Blogspot. Советы, трюки и секреты для Blogger.com блоггеров. Все для Blogspot.

Задача о рюкзаке (C#)

08 июня 2010, 21:43

Реализовать программу решения классической задаче динамического программирования – задачи о рюкзаке. Имеется набор из n предметов со стоимостями v1,v2,...,vn и весами w1,w2,...,wn соответственно. Также имеется рюкзак, способный вместить предметы с суммарным весом не более W. Необходимо выбрать и поместить в рюкзак такие предметы, чтобы суммарная их стоимость была максимальной. Визуализировать промежуточные шаги решения задачи*.
 
P.S. Может кому что пригодится но дп тут не реализовано.
 
Code:
 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO; //пространство имен для работы с файловыми потоками
 
 
namespace BackpackF1
{
    public partial class BackpackForm : Form
    {
 
        public BackpackForm()
        {
            InitializeComponent();
        }
        public static int maxCost=0; // максимальная стоимость
        public static int MaxWeight=0; // ограничение веса
        public static int n=0;  // количество элементов массива
        public static string strTable,symstr; // вспомогательный строки
        public static int count; // количество строк
        table form = new table();
       
        // Основная функция программы реализующая сам алгоритм, вызываемая при нажатие кнопки "Упаковка"
        private void start_Click(object sender, EventArgs e)
        {
            if (restrictionmas.Text == "" || restrictionmas.Text == "0")  // Проверка ввода
            {
                MessageBox.Show("Введите ограничение веса!");
                return;
            }
            if (dataBox.Text == "") // Проверка ввода
            {
                MessageBox.Show("Введите предметы!");
                return;
            }
        MaxWeight = Convert.ToInt32(restrictionmas.Text);
        count = 0;
        string t = dataBox.Text.Trim();
        string strName = "";
        int p = 1; bool w=false;
        // цикл для взятие из строки t (со всеми данными), только наименования предметов в strname
        for (int i = 0; i < t.Length; i++)
        {
            if (t[i] == '"')
            {
                p += 1;
                w = true;
            }
            if (p % 2 == 0 || w)
            {
                strName += t[i];
            }
            if (w && p % 2 != 0)
                strName += "\n";
            w = false;
          
        }
        // разбиение на массив имен
        string[] masName = strName.Split('\n');
        string[] str = t.Split(',', '\n');
        int b = 0;
        n = masName.Length;
        int[] c = new int[n];
        int[] m = new int[n];
        int[] a = new int[n];
        // Разбиение строки на массив масс и стоимостей
        for (int j = 0; j < str.Length && b+1 <= n; j++)
        {
            c[b] = Convert.ToInt32(str[j + 1]);
            m[b] = Convert.ToInt32(str[j + 2]);
            j = j + 2;
            b++;
        }
        search(0, a, c, m, MaxWeight, 0, 0);
        if (strTable == null) { MessageBox.Show("Вес всех предметов больше ограничения!"); return; }
        string[] strstrTable = strTable.Split('\n');
        result.Text = Convert.ToString(maxCost);
        maxCost = 0;
        form.Hide();
        form.grid.DataSource = null;
        form.grid.ColumnCount = n;
        // Заполнение наименования столбцов
        for (int i = 0; i < n; i++)
        {
            form.grid.Columns[i].HeaderText = masName[i];
        }
        string[] massym = symstr.Split(' ');
        form.grid.RowHeadersWidth = 120;
        // Добавление строки в таблицу
        for (int i = 0; i < count; i++)
        {
            form.grid.Rows.Add();
            resultBox.Clear();
            form.grid.Rows[i].HeaderCell.Value = massym[i];
            string buf = strstrTable[i];
            for (int j = 0; j < form.grid.Columns.Count-1; j++)
            {
                form.grid.Rows[i].Cells[j].Value = buf.Substring(j, 1);
                if (buf.Substring(j, 1) == "1")
                    resultBox.Text += masName[j] + "\n";
            }
        }
 
        strTable = "";
        butTable.Enabled = true;
    }
       /*  Функция search, получает: значение k - текущий элемент, масив a[] (взял не взял предмет),
           масcив стоимостей с[],масcив стоимостей m[],
           maxWeight  ограничение веса, currentWeight текущий вес,
           currentCost текущую стоимость   */
        static void search(int k, int[] a, int[] c, int[] m, int maxWeight, int currentWeight, int currentCost)
        {
            if (k >= n)
            {
                if (maxCost < currentCost && maxWeight >= currentWeight)
                {
                    maxCost = currentCost;
                    symstr += Convert.ToString(maxCost) + ' '; // swmstr хранит строку со стоимостями
                    output(a);// вызов функции вывода
 
                }
            }
            else
            {
                // Если по весу проходит, то прибовляем стоимость и сумарный вес вызываем рекурсивно функцию search
                if (currentWeight + m[k] <= maxWeight)      
                {
                    a[k] = 1;
                    search(k + 1, a, c, m, maxWeight, currentWeight + m[k], currentCost + c[k]);
                }
                // Иначе не берем и смотрим следующий элемент
                a[k] = 0;
                search(k + 1, a, c, m, maxWeight, currentWeight, currentCost);
 
            }
 
        }
        // Функция сохряняюшая значения масива a[] в строковую переменную strTable
        static void output(int[] a)
        {
            for (int i = 0; i < n; i++)
            {
              strTable +=Convert.ToString(a[i]);
            }
            strTable += "\n";
            count++;
        }
       private void ОткрытьToolStripMenuItem_Click(object sender, EventArgs e)
       {
            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            //если в окне диалога был выбран файл
            {
                string s = openFileDialog1.FileName; 
                // в переменную s запоминаем название выбранного файла
                StreamReader sr = new StreamReader(s);
                //создаем новый объект StreamReader и передаем ему переменную
                char f = sr.ReadToEnd()[0]; sr.Close();
                if (f == '?')
                {
                    StreamReader r = new StreamReader(s);
                    count = 0;
                    dataBox.Text = r.ReadToEnd();
                    //Читаем весь файл и записываем его в richTextBox1
                    string t = dataBox.Text.Trim();
                    int ind = t.IndexOf(' ');
                    restrictionmas.Text = t.Substring(1, ind - 1);
                    int tri = ind--;
                    ind++;
                    t = t.Substring(ind, t.Length - tri);
                    dataBox.Text = t.Trim();
                    r.Close();
                    // Закрываем поток
                }
                else MessageBox.Show("Неверный формат данных!");
             
            }
       
       }
       private void сохранитьToolStripMenuItem_Click(object sender, EventArgs e)
       {
           if (saveFileDialog1.ShowDialog() == DialogResult.OK)
            {
                //Создаем новый объект StreamWriter и передаем ему название выбранного файла
                StreamWriter sw = new StreamWriter(saveFileDialog1.FileName);
                //Содержимое richTextBox1 записываем в файл, дабавляе в начале ? и ограничение веса
                sw.WriteLine("?" + restrictionmas.Text + " " + dataBox.Text);         
                sw.Close();      //Закрываем поток
            }
// Перехватов Д. 09МОС(у)
       }
 
       // Вызов формы "О программе"
       private void оПрограммеРюкзакToolStripMenuItem_Click(object sender, EventArgs e)
       {
 
           About form = new About();
           form.Show();
          // Перехватов Д. 09МОС(у)
       }
       private void выходToolStripMenuItem_Click(object sender, EventArgs e)
       {
           Form.ActiveForm.Close();
       }
 
       // Блокирование ввода любых символов кроме цифр
       private void restrictionmas_KeyPress(object sender, KeyPressEventArgs e)
       {
           if ((e.KeyChar < 48 || e.KeyChar > 57) && e.KeyChar != 8)
               e.Handled = true;
       }
       // Очистка полей формы
       private void Clear_Click(object sender, EventArgs e)
       {
           dataBox.Clear();
           resultBox.Clear();
           restrictionmas.Clear();
           result.Text="";
           butTable.Enabled = false;
       }
        // Вызов формы альтернативного ввода
       private void Insert_Click(object sender, EventArgs e)
       {
           dataBox.Clear();
           Insert form = new Insert();
           form.Owner = this;
           form.ShowDialog();
           count = 0;
       }
       private void сохранитьРезультатToolStripMenuItem_Click(object sender, EventArgs e)
       {
           if (saveFileDialog1.ShowDialog() == DialogResult.OK)
           {
               StreamWriter sw = new StreamWriter(saveFileDialog1.FileName);
               //Создаем новый объект StreamWriter и передаем ему название выбранного файла
               sw.WriteLine(resultBox.Text);
               //Содержимое richTextBox1 записываем в файл
               sw.Close();      //Закрываем поток
           }
       }
       private void помощьToolStripMenuItem_Click(object sender, EventArgs e)
       {
           Help form = new Help();
           form.Owner = this;
           form.ShowDialog();
       }
       private void открытьРезультатToolStripMenuItem_Click(object sender, EventArgs e)
       {
           //если в окне диалога был выбран файл
           if (openFileDialog1.ShowDialog() == DialogResult.OK)
           {
               // в переменную s запоминаем название выбранного файла
               string s = openFileDialog1.FileName;
               //создаем новый объект StreamReader и передаем ему переменную s
               StreamReader sr = new StreamReader(s);
               //Читаем весь файл и записываем его в richTextBox1
               resultBox.Text = sr.ReadToEnd();
               sr.Close();     // Закрываем поток
           }
       }
 
       private void butExit_Click(object sender, EventArgs e)
       {
           BackpackForm.ActiveForm.Close();
       }
 
       private void butTable_Click(object sender, EventArgs e)
       {
           form.ShowDialog();
       }
    }
}
 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
 
namespace BackpackF1
{
    public partial class Insert : Form
    {
        public Insert()
        {
            InitializeComponent();
        }
// Перехватов Д. 09МОС(у)
        private void Addsub_Click(object sender, EventArgs e)
        {
            if (editName.Text == "" || editName.Text == "0")
            {
                MessageBox.Show("Введите наименование!");
                return;
            }
            if (editSym.Text == "" || editSym.Text == "0")
            {
                MessageBox.Show("Введите стоимость!");
                return;
            }
            if (editMas.Text == "" || editMas.Text == "0")
            {
                MessageBox.Show("Укажите массу!");
                return;
            }
            BackpackForm form = (BackpackForm)this.Owner;
            string q = form.dataBox.Text;
            q += "\"" + editName.Text.Trim()+"\"" + " , " + editSym.Text.Trim() + " , " + editMas.Text.Trim() + "\n";
            form.dataBox.Clear();
            form.resultBox.Clear();
            editName.Clear();
            editSym.Clear();
            editMas.Clear();
            form.dataBox.Text = q;
        }
    }
}

 
 
 
 
Задача о рюкзаке (C#)