Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Полный перебор 
:(
    Опции темы
3.14zDoS
Дата 3.12.2004, 13:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.11.2004

Репутация: нет
Всего: нет



Есть файл(НазваниеПредмета, Вес, Стоимость):
предмет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) а стоимость была максимальна.
Меня интересует метод Монте-Карло. Немогу в него врубится.
PM MAIL   Вверх
podval
Дата 3.12.2004, 15:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62



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


Отбрасывая всякие упоминания о StringGrid, обратимся к методу Монте-Карло.
С какого места непонятно?
PM WWW ICQ   Вверх
podval
Дата 3.12.2004, 15:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62



Я бы предложил такое направление.

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

Допустим, обозначим 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
PM WWW ICQ   Вверх
~FoX~
Дата 6.12.2004, 17:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


НЕ рыжий!!!
****


Профиль
Группа: Участник Клуба
Сообщений: 2819
Регистрация: 8.10.2003
Где: Зеленоград

Репутация: 2
Всего: 68



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


--------------------
user posted image
…множественность никогда не следует полагать без необходимости…
PM MAIL WWW ICQ Jabber   Вверх
~FoX~
Дата 7.12.2004, 10:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


НЕ рыжий!!!
****


Профиль
Группа: Участник Клуба
Сообщений: 2819
Регистрация: 8.10.2003
Где: Зеленоград

Репутация: 2
Всего: 68



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 заполняется не из файла, но это ты сам допишишь.
Я сортил методом пузырька, ты можешь использовать любой другой алгоритм.


--------------------
user posted image
…множественность никогда не следует полагать без необходимости…
PM MAIL WWW ICQ Jabber   Вверх
~FoX~
Дата 7.12.2004, 10:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


НЕ рыжий!!!
****


Профиль
Группа: Участник Клуба
Сообщений: 2819
Регистрация: 8.10.2003
Где: Зеленоград

Репутация: 2
Всего: 68



Вариант с полным перебором выложу попозже, секйчас работы много.


--------------------
user posted image
…множественность никогда не следует полагать без необходимости…
PM MAIL WWW ICQ Jabber   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0718 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.