3. Акулич И.Л., Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с.
4. Габасов Р., Кириллова Ф. М. Основы динамического программирования. — Мн.: Изд-во БГУ, 1975. — 262 с.
Приложение
using System;
using System.Collections.Generic;
using System.Text;
namespace odgig
{
class rukzak
{
publicint[] x; // массивкник (хромосома)
privateint f;
publicdouble q;
public rukzak()
{
x = newint[Constants.N]; //выделяемпамятьдлямассивакниг
f = 0;// целевая функция
q = 0;
}
publicbool check()// проверка на допустимость
{
int sum = 0;
for (int i = 0; i < Constants.N; i++) sum += Program.a[i] * x[i];//сумма объемов предметов, положенных в рюкзак, фитнесс - функция
if (sum > Constants.R) returnfalse;// если сумма больше вместительности рюкзака,не допустимо
returntrue;
}
publicint g()//вычислениецелевойфункции
{
int sum = 0;
for (int i = 0; i < Constants.N; i++) sum += Program.c[i] * x[i];// формуладлявычисленияцелевойфункции
return sum;
}
publicint get_f()//обвертка
{
return f;
}
publicvoid set_f()//обвертка
{
f = g();
}
publicvoid copy(rukzak r)//функциякопирования
{
for (int i = 0; i < r.x.Length; i++) this.x[i] = r.x[i];
this.f = r.f;
}
publicvoid gadnyi()
{
elem[] ruk = new elem[Constants.N];
elem o = new elem();
for (int i = 0; i < Constants.N; i++) ruk[i] = new elem();
for (int i = 0; i < Constants.N; i++)
{
ruk[i].index = i;
}
for (int i = 0; i < Constants.N; i++)
{
if (Program.a[i] > 0)
ruk[i].averge = (double)(Convert.ToDouble(Program.c[i]) / Program.a[i]);
}
Array.Sort(ruk, new ElemMoreComparator());
for (int l = 0; l < Constants.N; l++)
{
this.x[ruk[l].index] = 1;
q = q + Program.a[ruk[l].index] * this.x[ruk[l].index];
if ((q < Constants.R) || (q == Constants.R)) f = f + Program.c[ruk[l].index] * this.x[ruk[l].index];
else
{
q = q - Convert.ToDouble(Program.a[ruk[l].index] * this.x[ruk[l].index]); this.x[ruk[l].index] = 0; break;
}
}
Console.Write("решение:(");
for (int l = 0; l < Constants.N; l++) Console.Write("{0}", this.x[l]);
Console.Write(")");
Console.WriteLine("целеваяфункция:{0}", f);
}
publicvoid Mutation(double Q)//мутация
{
rukzak mut = new rukzak();
mut.copy(this);
while (true)
{
for (int r = 0; r < 3; r++)
{
int border = (int)Program.myu(0, Constants.N - 1);//случайнымобразомвыбираемномермутирующейхромосомы
if (mut.x[border] == 0) mut.x[border] = 1;
else mut.x[border] = 0;
}
mut.set_f();
if (mut.check())
{
if (mut.get_f() > this.get_f())
{
this.copy(mut);
Console.WriteLine("целеваяф-ия:{0}", this.get_f());
break;
}
else
{
Constants.pMutation = Math.Exp(Convert.ToDouble(-(this.get_f() - mut.get_f()) / Q));
if (Program.myu(0, 1) < Constants.pMutation)
{
this.copy(mut);
Console.WriteLine("целеваяф-ия:{0}", this.get_f());
break;
}
else
{
mut.copy(this);
}
}
}
else mut.copy(this);
}
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace odgig
{
class Program
{
staticpublicint[] c;
staticpublicint[] a;
staticpublicRandom rand = newRandom();
staticpublicdouble myu(double a, double b)
{
if (a > b)
{
Console.WriteLine("Первый параметр больше второго");
System.Environment.Exit(0);
}
double y = rand.NextDouble();
return (a + (b - a) * y);
}
staticvoid Main(string[] args)
{
StreamReader sReader = newStreamReader("inp.txt");
string[] str = sReader.ReadLine().Split(' ');
Constants.N = int.Parse(str[0]);
Constants.R = int.Parse(str[1]);
Program.c = newint[Constants.N];
Program.a = newint[Constants.N];
Console.Write("Цена:");
for (int j = 0; j <Constants.N; j++)
{
Program.c[j] = int.Parse(str[j + 2]);
Console.Write("{0} ", Program.c[j]);
}
Console.WriteLine();
Console.Write("Вес:");
for (int j = 0; j < Constants.N; j++)
{
Program.a[j] = int.Parse(str[j + Constants.N + 2]);
Console.Write("{0} ", Program.a[j]);
}
Console.WriteLine();
sReader.Close();
Console.WriteLine("Числопредметов:{0} Объемранца:{1}", Constants.N, Constants.R);
DateTime t1 = DateTime.Now;
rukzak gruk = new rukzak();
gruk.gadnyi();
double Q = 10;
while(true)
{
double a = 0.9;
Q = Q * a;
gruk.Mutation(Q);
DateTime t2 = DateTime.Now;
TimeSpan tProgram = t2 - t1;
if (Q < 0.5) Console.WriteLine("Время:" + Convert.ToString(tProgram));
}
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace odgig
{
class elem
{
publicdouble averge;
publicint index;
}
publicclass ElemMoreComparator : IComparer
{
privateconstdouble EPS = 1e-9;
#region IComparer Members
intIComparer.Compare(object x, object y)
{
elem e1 = (elem)x;
elem e2 = (elem)y;
double delta = e2.averge - e1.averge;
if (System.Math.Abs(delta) <=EPS)
return 0;
return System.Math.Sign(delta);
}
#endregion
}
}