Задача о ранце

[werder_ua]

Очень надо прогу которая решаєт задачу о ранце
Дан набор предметов.
Каждий имеєт свой вес и ценность. На входе задайотса максимальная маса рюкзака, предмети и их характеристика (маса, ценность).
Нужно загрузить ранец максимальною допустимой масой предметов с найбольшей ценностю.
реализация должна бить на паскале или делфі.

ПОМОГИТИ ПОЖАЛУСТА КТО МОЖЕТ!

[Stilet]

Хы... Это делается просто: В БД вбиваются данные, а потом индексируются по весам и характеристикам. После берутся предметы пока их сумарная масса не превышает массу Х.
Впрочем это можно забабахать сортировкой массива предметов.
Смысл ясен?

[werder_ua]

нет можно подробней пожалуста

[Serge_Bliznykov]

Stilet, ой, Виталий, боюсь, что не всё так просто и радужно ;(
Для новичка, думаю, сойдёт. но вот в реальной практике.. ;(

дело в том, что тут обязательно перебирать каждый предмет с каждым (причём с одним, с двумя, с тремя и т.д.) вычислительная мощность потребуется абсолютно невообразимая ;(
поясню свою мысль примером:
пусть рюкзак вмещает 5 кг.
у нас есть (предмет, вес, ценность):

предмет1 4кг 100
предмет2 2кг 60
предмет3 2кг 60

очевидно, что Предметы 2+3 дадут больше, чем 1..
(т.е. при большом количестве предметов, сумма малых предметов может быть больше, чем один большой!)

[Hollander]

Кстати, этот на этой задаче основан метод криптографии, уже честно говоря вылетел из головы.
По поводу реализации, вот на C++: http://ru.wikipedia.org/wiki/%D0%97%...BD%D1%86%D0%B5
Вот на Delphi: http://plagiata.net.ru/?p=966

[Stilet]

перебирать каждый предмет с каждым

Этак ты на алгоритм сортировки выйдешь )

werder_ua

ЗАписываешь в базу данных предмети и их характеристики (маса, ценность).
Потом сортируеш запросом по массе и ценности, и выбираешь из полученного набора с сумированием массы.

[werder_ua]

Спасибо за совети. Я посмотрел всьо отлично но прога написаная на Delphi счетаєт только конткретную суму мас предметов, тоесть не считаєт приблизетельную масу предметов.
Например
Максимальная маса рюкзака 12
Дано предмети с масами:
3
4
6
то результату програма не видаст
но если предмети имеют маси:
2
4
6
5
То результат будет
2 4 6.

А С++ я не понимаю савсем

Нудно чтоби имелось в виду и ценность предметов а не только их вес
Сделайте пожалуста програмку ну очень надо
За мной не постоит
Если что стучите в аську 405286740

Вот код програми на Delphi:

unit Unit13;

interface

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

type
  TForm13 = class(TForm)
    Edit1: TEdit;
    Label1: TLabel;
    Edit2: TEdit;
    Label2: TLabel;
    StringGrid1: TStringGrid;
    Label3: TLabel;
    Memo1: TMemo;
    Label4: TLabel;
    Button1: TButton;
    Button2: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Edit1Change(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form13: TForm13;

implementation

{$R *.dfm}

procedure TForm13.Button1Click(Sender: TObject);
var a,b:array[1..100] of integer;
   n:byte;
   sum:integer;
   f:boolean;
   i,j,k,h,s,m,z:integer;
   otvet: string;
begin
  //Ввод данных
  n := StrTointDef(Edit1.Text, 0);
  if n = 0 then
  begin
    ShowMessage('Не задано количество предметов');
    exit
  end;
  with StringGrid1 do
    for i := 1 to n do
      a[i] := StrTointDef(Cells[1,i], 0);
  sum := StrTointDef(Edit2.Text, 0);
  if sum = 0 then
  begin
    ShowMessage('Не задан максимальный вес ранца');
    exit
  end;
otvet := 'В ранец необходимо поместить предметы: ';
For I := N Downto 1 Do
 Begin
  B[1] := I;
  H := 1;
  K := Sum - A[I];
  F := False;
  Repeat
   For J := B[H]-1 Downto 1 Do
    Begin
     If A[J] <= K Then
      Begin
       Inc(H);
       B[H] := J;
       Dec(K, A[J]);
      End;
       If K = 0 Then
        Begin
         For M := 1 to H Do otvet := otvet + IntToStr(A[B[M]]) + ' ';
         Inc(K, A[B[H]]);
         Dec(H);
        End;
    End;
   F := True;
   For M := H Downto 2 Do
     Begin
       If B[M] <> H-M+1 Then
       Begin
        F := False;
        Dec(B[M]);
    H := M;
        K := Sum;
        For Z := 1 to H Do
         Dec(K, A[B[Z]]);
        Break;
       End;
     End;
  Until F;
 End;
memo1.Lines.Add(otvet)
end;

procedure TForm13.Button2Click(Sender: TObject);
begin
  close
end;

procedure TForm13.Edit1Change(Sender: TObject);
  var i, n: integer;
begin
  n := StrTointDef(Edit1.Text, 0);
  with StringGrid1 do
  if (n > 0) and (n <= 100) then
  begin
    RowCount := n + 1;
    for I := 1 to RowCount - 1 do
    begin
      Cells[0, i] := IntToStr(i);
    end;
  end;
end;



procedure TForm13.FormCreate(Sender: TObject);
  var i: Integer;
begin
  with StringGrid1 do
  begin
    Cells[0,0] := 'Номер предмета';
    Cells[1,0] := 'Вес предмета';
    for I := 1 to RowCount - 1 do Cells[0, i] := IntToStr(i);
    Cells[1,1] := '2';
    Cells[1,2] := '3';
    Cells[1,3] := '4';
    Cells[1,4] := '7';
  end;
end;

end.

СДЕЛАЙТЕ ПОЖАЛУСТА Я В ДОЛГУ НЕ ОСТАНУСЬ!!!

[Alar]

Сообщение от Hollander

Вот на Delphi: http://plagiata.net.ru/?p=966

Задача о ранце. Реализация на Delphi
Рубрика: Программирование 10 Дек 2008

Такое интересное название эта задача получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём или вес всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами „стоимость“ и „вес“, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес. Рассмотрим решение задачи о ранце на Delphi.

Описание правильное. только вот стоимость предметов вообще не учитывается в решении. да и просто по весу распределяет не правильно

[k1r1ch]

Это классический пример динамического программирования. Вот тут посмотрите 5 и 6 видеокурсы, там есть эта задача.