Помогите чайнику!!!

[Dronishe]

Добрый день! Недавно в Вузе начали изучать Турбо Паскаль, и на тему курсовой выпала такая задача:
"Имеется рюкзак, в котором можно переносить груз не более определенного веса. Задан набор предметов имеющих определенные веса. Определить такой вариант наполнения рюкзака, чтобы суммарный вес положенных в рюкзак предметов точно совпадал с грузоподьмностью рюкзака. "
Можете дать какие-нибудь советы по выполнению? Если кто напишет примерный код, по гроб буду благодарен!!!

[SergeyS]

задачка очень простая, решается рекурсивно, путём полного перебора вариантов.
создай двумерный массив, где первое измерение будет означать вес предмета, а второе измерение будет служить признаком - находится предмет в рюкзаке или нет.
Создай функцию, которая в цикле будет проходить по всему массиву и кладёт в рюкзак очередной свободный предмет и проверяет общий вес предметов в рюкзаке, если он меньше заданного то пусть вызывает саму себя, если равен вернуть истина (решение найдено), если больше то пусть вернёт ложь (решение неверное). Задачу можно расширить до возможности поиска максимально возможного веса.

[Dronishe]

Все впринципе понятно, но у меня проблема с массивами, чет не понимаю я их
Поможешь написать массив? Очень надо! 100000 зарание спасибо!!!

[SergeyS]

Код: Выделить всё

const
  { Данные константы можно определить как переменные и задавать в программе }
  N = 5; { Количество различных предметов }
  W = 20; { Вместимость рюкзака }

type
  TWeight = record
    weight: Integer; {сам вес}
    used: Boolean; {признак нахождения предмета в рюкзаке}
  end;

var
  MaxWeight: Integer;
  weights: array[1..N] of TWeight;

function CalcWeight: Integer;
var
  i: Integer;
begin
  Result := 0;
  for i := 0 to N do
    if weights[i].used then Result := Result + weights[i].weight;
end;

function FindSolution(weight: Integer): Boolean;
var
  i: Integer;
begin
  Result := True;
  for i := 1 to N do begin
    if not weights[i].used then begin
      { предмет не в рюкзаке, положим его }
      weights[i].used := True;
      if CalcWeight < weight then begin
        if CalcWeight > MaxWeight then
          { запоминаем максимальный вес, положенный в рюкзак }
          MaxWeight := CalcWeight;
        
        { вес ещё недобрали, искать дальше }
        if FindSolution(weight) then
          { нужный вес найден }
          Exit
      end else
      if CalcWeight = weight then
        { Решение найдено }
        Exit;
      { с данным весом решение не найдено, убераем его }
      weights[i].used := False;
    end;
  end;
  { Раз дошли до конца цикла, значит решения нет }
  Result := False;
end;

var
  i: Integer;
begin
  MaxWeight := 0; { заодно найдём максимально возможный вес, который мы
  можем положить в рюкзак, на случай если точного решения не будет найдено }

  Randomize;
  for i := 1 to N do begin
    weights[i].weight := 1 + Round(Random(50));
    weights[i].used := False;
    Write(weights[i].weight:4);
  end;
  WriteLn;

  if FindSolution(W) then begin
    { Решение найдено, распечатать }
    WriteLn('Solution (', CalcWeight, '):');
    for i := 1 to N do
      if weights[i].used then
        Write(weights[i].weight:4);
    WriteLn;
  end else begin
    { Точного решения не найдено, выведем максимально возможный вес }
    FindSolution(MaxWeight);
    WriteLn('Solution (', CalcWeight, '):');
    for i := 1 to N do
      if weights[i].used then
        Write(weights[i].weight:4);
  end;

  ReadLn;
end.

[Dronishe]

Спасибо ОГРОМНОЕ!!! Попробую код на работоспособность позже но чет даже не сомневаюсь что он не работает опыт

[somewhere]

SergeyS, не мешайте, пожайлуста, в кучу Delphi и Pascal.
Указанный способ работает только в Delphi

Result := 0;

Dronishe, используйте заместо этого название функции, в контексте которой размещен возврат результата.
ВНИМАНИЕ!!!
Следующий код, после исправления будет неработоспособен:

Код: Выделить всё

function CalcWeight: Integer;
var
  i: Integer;
begin
  CalcWeight := 0;
  for i := 0 to N do
    if weights[i].used then CalcWeight := CalcWeight + weights[i].weight;
end;

Причиной является рекурсивный вызов самой себя (CalcWeight := CalcWeight + weights.weight)
Его можно заменить на

Код: Выделить всё

function CalcWeight: Integer;
var
  i,s: Integer;
begin
  s := 0;
  for i := 0 to N do
    if weights[i].used then s := s + weights[i].weight;
  CalcWeight := S;
end;

[Dronishe]

Все спасибо! Программа работает на 100% немного исправлений пришлось внести, ну эт ниче!
Еще раз спасибо!

[Dronishe]

Народ у меня появилось еще 2 проблемы!!!
Препод захотел, чтоб ввод данный осуществлялся из файла и результаты записывал в другой. Причем он сказал что Random в данный программе не подходит!
Что делать? Я опять надеюсь на вашу помощь! Плиз хелп!

[Хыиуду]

Создать текстовый файл с весами (ручками), потом из этого файла в цикле считать
for i:=1 to N do read(f_input, weights.weight);
После выполнения программы создать выходной файл и в него все вывести
for i := 1 to N do
if weights.used then
Write(f_output, weights.weight:4);
Как открывать файлы для чтения и записи - написано в любом учебнике, это азы Паскаля.

[Dronishe]

народ у меня чета нихера не получается, какую-то ошибку пишет

Program Kurs;
const
N = 5;
W = 30;
Type
TWeight = record
weight: Integer;
used: Boolean;
end;
Type
FileName= String[20];
InfileName, ResFileName: FileName;
f_input:text;
F2:text;
var
MaxWeight: Integer;
weights: array[1..N] of TWeight;

function CalcWeight: Integer;
var
i,s: Integer;
begin
s := 0;
for i := 0 to N do
if weights.used then s := s + weights.weight;
CalcWeight := S;
end;

function FindSolution(weight: Integer): Boolean;
var
i: Integer;
Result :boolean;
begin
Result := True;
WriteLn('Vvedite imya faila c vesom predmetov');
ReadLn(InFileName);
Assign(f_input, InFileName);
Reset(f_input);
for i:=1 to N do read(f_input, weights.weight);
if not weights.used then
begin
weights.used := True;
if CalcWeight < weight then begin
if CalcWeight > MaxWeight then
MaxWeight := CalcWeight;

if FindSolution(weight) then
Exit
end else
if CalcWeight = weight then
Exit;
weights.used := False;
end;
end;
Result := False;
end;

var
i: Integer;
begin
MaxWeight := 0;
for i := 1 to N do begin
weights.weight := 1 + weights);
weights.used := False;
Write(weights.weight:4);
end;
WriteLn;

if FindSolution(W) then begin
WriteLn('Solution (', CalcWeight, '):');
for i := 1 to N do
if weights[i].used then
Write(weights[i].weight:4);
WriteLn;
end else begin
FindSolution(MaxWeight);
WriteLn('Solution (', CalcWeight, '):');
for i := 1 to N do
if weights[i].used then
Write(weights[i].weight:4);
end;
ReadLn;
end.