Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Полный перебор


Автор: 3.14zDoS 3.12.2004, 13:57
Есть файл(НазваниеПредмета, Вес, Стоимость):
предмет1 1500 200
предмет2 2000 100
предмет3 1500 200
предмет4 2500 100
предмет5 1000 200
предмет6 2500 100
предмет7 1500 200
предмет8 500 100
Как наполнить StringGrid так чтобы не превышалась грузоподъемность(5000) а стоимость была максимальна.
Меня интересует метод Монте-Карло. Немогу в него врубится.

Автор: podval 3.12.2004, 15:24
Модератор: Эта тема клонирована уже дважды под разными названиями в разных разделах.
В чем все-таки проблема?


Отбрасывая всякие упоминания о StringGrid, обратимся к методу Монте-Карло.
С какого места непонятно?

Автор: podval 3.12.2004, 15:48
Я бы предложил такое направление.

Поскольку все переменные в задаче целочисленные, то и применять надо целочисленные методы.

Допустим, обозначим Ci - множество стоимостей, mi - множество масс i-х предметов.

Xi - управляемые переменные, принимающие значение 1, если i-й предмет включен в оптимальный план, и 0, если не включен.

Имеем целевую функцию:

Код

SUM (Xi * Ci)  --> max
 i

при условии

SUM (Xi * mi)  <= M  ,
 i

где M - максимальная общая масса.

Выглядит идиотски smile

О методах решения можно справиться в книге Вагнер. Исследование операций. Т. 2.
В основном они все сводятся к частичному перебору вариантов.

Кое-что здесь есть в качестве введения: http://optimizer.by.ru/implicits.htm

Автор: ~FoX~ 6.12.2004, 17:17
3.14zDoS
Полный перебор тебе даст оптимальный вариант/ты
Но если это не кртично, то можно посчитать удельную стоимость товара - вес/цена.
Отсортировать по убыванию. Взять предмет с самой большой уд.стоимостью и прибавляя к нему следующий товар проверять, что М<5000. Если да, то берем следующи товар, если нет, берем товар следующий за ним. Это будет быстрее, но вероятно что у тебя останеться пустое место (М строго меньше 5000).
Добавлено @ 17:18
3.14zDoS
Завтра выложу код на паскале если хочешь с решением полным перебором и варианта с удельной стоимостью. "А сейчаз пора спать" smile

Автор: ~FoX~ 7.12.2004, 10:34
3.14zDoS

Вот пример с удельной стоимостью.
Код

unit Unit1;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls, ComCtrls, Grids;

type
 TForm1 = class(TForm)
   Button1: TButton;
   StringGrid1: TStringGrid;
   Label1: TLabel;
   Label2: TLabel;
   procedure FormCreate(Sender: TObject);
   procedure Button1Click(Sender: TObject);

 private
   { Private declarations }
 public
   { Public declarations }
 end;

 procedure CreateUCost();
 procedure FullSort();
 procedure FullGrid();
type
 TGen = record
   Name: string[255];
   mass: integer;
   cost: integer;
   ucost: real;
   zap: Boolean;
end;

var
 Form1: TForm1;
 MyGen: array of TGen;
implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
 SetLength(MyGen, 8);

 MyGen[0].Name := 'Tovar1';
 MyGen[1].Name := 'Tovar2';
 MyGen[2].Name := 'Tovar3';
 MyGen[3].Name := 'Tovar4';
 MyGen[4].Name := 'Tovar5';
 MyGen[5].Name := 'Tovar6';
 MyGen[6].Name := 'Tovar7';
 MyGen[7].Name := 'Tovar8';

 MyGen[0].mass := 1500;
 MyGen[1].mass := 2000;
 MyGen[2].mass := 1500;
 MyGen[3].mass := 1500;
 MyGen[4].mass := 2500;
 MyGen[5].mass := 1000;
 MyGen[6].mass := 1500;
 MyGen[7].mass := 500;

 MyGen[0].cost := 200;
 MyGen[1].cost := 100;
 MyGen[2].cost := 200;
 MyGen[3].cost := 100;
 MyGen[4].cost := 200;
 MyGen[5].cost := 100;
 MyGen[6].cost := 200;
 MyGen[7].cost := 100;

 MyGen[0].ucost := 0;
 MyGen[1].ucost := 0;
 MyGen[2].ucost := 0;
 MyGen[3].ucost := 0;
 MyGen[4].ucost := 0;
 MyGen[5].ucost := 0;
 MyGen[6].ucost := 0;
 MyGen[7].ucost := 0;


 MyGen[0].zap := False;
 MyGen[1].zap := False;
 MyGen[2].zap := False;
 MyGen[3].zap := False;
 MyGen[4].zap := False;
 MyGen[5].zap := False;
 MyGen[6].zap := False;
 MyGen[7].zap := False;

end;

procedure CreateUCost();
var
 i: integer;
begin
 for i := 0 to 7 do begin
   MyGen[i].ucost := MyGen[i].cost/MyGen[i].mass;
 end;
end;

procedure FullSort();
var
 i, k: integer;
 temp: TGen;
begin
 for i := 0 to 6 do
   for k := i to 7 do begin
     if MyGen[i].ucost < MyGen[k].ucost then begin
       temp := MyGen[i];
       MyGen[i] := MyGen[k];
       MyGen[k] := temp;
     end;
   end;
end;

procedure FullGrid();
var
 i, msum, sum: integer;
 s: string;
begin

 if MyGen[0].mass <= 5000 then begin
   MyGen[0].zap := True;
   msum := MyGen[0].mass;
 end;

 for i := 0 to 7 do begin
   if msum + MyGen[i].mass <= 5000 then begin
     msum := msum + MyGen[i].mass;
     MyGen[i].zap := True;
   end;
 end;
 for i := 0 to 7 do begin
   if MyGen[i].zap = true then begin
     Form1.StringGrid1.Cells [1, i+1] := MyGen[i].Name;
     sum := sum + MyGen[i].cost;
   end;
 end;
 Form1.Label1.Caption := intTostr(msum);
 Form1.Label2.Caption := intTostr(sum);
end;


procedure TForm1.Button1Click(Sender: TObject);
begin
CreateUCost;
FullSort;
FullGrid;
end;

end.


Прости, что без коментариев, какие то траблы с кодировкой.

Тип TGen заполняется не из файла, но это ты сам допишишь.
Я сортил методом пузырька, ты можешь использовать любой другой алгоритм.

Автор: ~FoX~ 7.12.2004, 10:52
Вариант с полным перебором выложу попозже, секйчас работы много.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)