Срочно нужна реализация решения задачи о рюкзаке.Желательно в исходных кодах на дельфи. Текст задачи : Имеется набор предметов различного веса и стоимости.Определить группу предметов максимальной общей стоимости,если общий вес рюкзака не должен превышать заданного значения. Дайте ссылочку или код.

Молодой человек, учиться надо самому, а не нахаляву.

Очередной хитрозадый студент ?

Да,студент. Но не хитрозадый,учусь в техническом вузе,на гуманитарной специальности.Поэтому не хочется чтоб меня отчислили из-за какого-то программирования(((

А что за ВУЗ ?

ОмГТУ ФГО Омск

Программирование - оно не "какое-то"!

Ну вообще-то главная задача в программировании, научить вас грамотно составлять алгоритмы.

Ну вообще-то главная задача в программировании, научить вас грамотно составлять алгоритмы.

Что кстати не плохо надо уметь делать гуманитариям типа - юристы, экономисты и т.д.

Эт точно! Учат же технарей основам менеджмента или там социологии. И ничего, не загнулись соц. исследование провести или бизнес-план наклепать

БОЛЬШОЕ ВАМ СПАСИБО! Я в принципе просил кинуть в меня кодом,или на крайний случай алгоритмом, ибо закодить это не проблема.Вы же развели дискуссию кто что должен уметь,хитрозадый я или нет.Но дело сделано,программа готова,причем моими силами.Правда пришлось посидеть над книгами.Может и на пользу,не спорю.А вообще, каждый должен заниматься своим делом.IMHO.Так что господа программеры получите под дых,ибо как говориться "трындеть-не мешки ворочать" и помочь мне вы не в состоянии, а базары тереть в форумах много ума не надо

P.S. Никого не хочу оскорбить,просто примите критику достойно

Вы же развели дискуссию кто что должен уметь,хитрозадый я или нет.Но дело сделано,программа готова,причем моими силами.Правда пришлось посидеть над книгами.Может и на пользу,не спорю.А вообще, каждый должен заниматься своим делом.IMHO.

Если ты учишься и программирование входит в учебную программу то в данный момент это твое дело.

Так что господа программеры получите под дых,ибо как говориться "трындеть-не мешки ворочать" и помочь мне вы не в состоянии, а базары тереть в форумах много ума не надо

Помочь чем? Программу за тебя написать? Дык ведь это того... денюжек стоит

программа готова,причем моими силами.Правда пришлось посидеть над книгами

Твои труды даром не пропадут. Поверь

Точно,не пропадут.Но пропало время((( Но "программирование" не входит в программу,а"информатика" входит.А это,как оказалось обширнейшая тема)))))))))))))))))))))))

Видно Вам сильно промыли мозги, это называется Математика, а конкретнее Математическое программирование, которое к Delphi, как и вообще к компьютерам никакого отношения не имеет. Причем тут Информатика, которая используется данный мат.аппарат ?

Может и промыли мозги.Но сей инцидент имеет место

Ща покумекаю... Список вещей - произвольный естественно???

а количество предметов в рюкзаке так же не ограничевается...

Совершенно вернос интересом посмотрю на другие варианты решения и покажу свой(если надо).

>Может и промыли мозги.Но сей инцидент имеет >место

Каждый должен делать свои домашние задания самостоятельно. Тролли в Usenet ведут себя и то более умно, недавно один пытался получить код для решения n-queens, но не стал никого оскорблять и говорить "господа программеры сели в лужу", а сказал, что это якобы для проекта надо. Но Вы видно не столь умны, чтобы представить эту задачу в таком виде.

Уважаемый, я не собирался что-то там придумывать и кого-то обманывать. Лично Вам : разговаривать попусту умеет практически любой, в том числе и Вы. Что-то сделать - сомневаюсь. Как говориться "после драки кулаками не машут", а Вы этим как раз занимаетесь. Если Вам не хватает сил и прочих факторов для самореализации не стоит писать бессмысленные сообщения. ИМХО для этого существуют разделы типа "Флейм".
З.Ы. Это мой единственный ответ Вам. Если хотите продолжить "обмусоливание",могу дать ссылку в место, где вы утолите свою жажду в пустословии. Удачи

Мха-ха-ха-ха! Красиво звоните, по риторике наверное 5+ ;-)

Да,"отлично",и по другим предметам тоже. Только я не "звоню", а излагаю своё мнение. Я,смею заметить никого лично не оскорбил, просто немного покритиковал программеров, которые отписались выше. Вы же, сравнивая меня с троллями, меня оскорбили, принизив мою фантазию и умственные способности. Видимо, у Вас свои критерии оценки умственных способностей...Ну да ладно. Я так понимаю себя Вы причисляете к Программистам, хотя я программу-то написал!хоть я и специалист по связям с общественностью, а вы-Кодер...Назвав меня "хитрозадым" и т.д., ни один не дал ни алгоритма, ни кода, ни даже ссылки на что-то подобное...
З.Ы. Могу предоставить два варианта решения данной задачи[1-й-попроще,2-й-посложнее]

> Да,"отлично",и по другим предметам тоже.
Good for you.

>Я,смею заметить никого лично не оскорбил, просто >немного покритиковал программеров, которые >отписались выше.
Так что господа программеры получите под дых,ибо как говориться "трындеть-не мешки ворочать" и помочь мне вы не в состоянии, а базары тереть в форумах много ума не надо

Надо думать это было не оскорбление ;-)

>Вы же, сравнивая меня с троллями, меня >оскорбили, принизив мою фантазию и умственные >способности.
Скорее всего Вы преувеличиваете мои способности. Извините, что из-за меня Ваша фантазия и способности понизились.

>Я так понимаю себя Вы причисляете к >Программистам, хотя я программу-то написал!

Вы и так должны были ее написать, Вам тут помогли немного, стимул дали и самооценка у Вас повысилась вон как ;-) а Вы даже спасибо не сказали!

>хоть я и специалист по связям с общественностью, >а вы-Кодер

Кодер из Вас наверняка получился бы лучше, чем специалист по связям с общественностью. Почему Вы решили, что я - кодер, а не другой специалист по связям с общественностью (конкурент так сказать) ? ;-)

>наазвав меня "хитрозадым" и т.д., ни один не дал >ни алгоритма, ни кода, ни даже ссылки на что-то >подобное

Я же мат.программирование упоминал, Вы невнимательно читали. Нельзя же быть таким обидчивым. Зато как быстро сами задачу решили и опыт получили.

>Могу предоставить два варианта решения данной >задачи

Не верю ! ;-)

Тем более смешно, что просто набрав на Google слова "задача о рюкзаке" можно было получить как минимум три источника, в которых подробно описано решение этой задачи, есть блок-схемы и т.п. Но Вы конечно выбрали самый сложный путь ;-)

unit unit1;

interface

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

type
TForm1 = class(TForm)
Button1: TButton;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label9: TLabel;
Label10: TLabel;
Label11: TLabel;
memo1: TMemo;
memo2: TMemo;
memo3: TMemo;
Label8: TLabel;
Label12: TLabel;
Label13: TLabel;
Label5: TLabel;
Label6: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
item: array[0..30] of integer;
val: array[0..1000,0..1000] of integer; {динамические массивы}
take: array[0..1000,0..1000] of boolean;
v,w: array[1..1000] of integer; {ценность и вес предметов}
n, TotalW: integer; {кол. предметов, максимальный вес}
weight, j, i: integer; {переменные циклов}
s:string;
implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin

begin
{читаем входные данные}
n:=Memo1.Lines.Count;
TotalW:=strtoint(edit2.text);
for i:=0 to n-1 do
begin
w[i+1]:=strtoint(memo2.Lines.Strings[i]);
v[i+1]:=strtoint(memo3.Lines.Strings[i]);
end;
{делаем начальную инициализацию для веса 0}
for i:=0 to n do begin
val[0,i] := 0;
take[0,i] :=false;
end;
for weight:=1 to TotalW do val[weight,0] := 0;
for weight := 1 to TotalW do
for i := 1 to N do
if (w[i]>weight) {если вещь не влезет}
{или лучше ее не брать}
or ( val[weight, i-1] >= val[weight-w[i],i-1] + v[i] )
then begin {то не берем ее}
val[weight,i] := val[weight,i-1]; {оптимум тот же, что для 1..i-1}
take[weight,i] := false; {отмечаем, что вещь i не взята}
end
else
begin
{оптимум := оптимум для веса weight-w[i] и использования вещей 1..i-1
+ цена вещи i, которую мы берем}
val[weight,i] := (val[weight-w[i],i-1] + v[i]);
take[weight,i] := true; {отмечаем, что вещь i взята}
end;
{вывод результатов}
begin
label13.Caption:=inttostr(val[TotalW, N]);
weight := TotalW;
j:=0;
s:='';
for i := N downto 1 do
if take[weight, i] then
begin
item[j]:=i;
s:=s+' '+inttostr(item[j]);
j:=j+1;
weight := weight - w[i];
end;
label8.Caption :=IntToStr(weight);
label5.Caption :=s;//IntToStr(item[j]);
end;
end;
end;
end.

Это простой вариант[первоначальный]
З.Ы. Скомпилировать и сделать интерфейс надеюсь сможете. Не собираюсь более Вас ни в чем убеждать. Я никого не пытался оскорблять той фразой, которую Вы цитировали.Спасибо я сказал [перечитайте 11-й пост с начала,там же увидите что мои пояснения к фразе,которую Вы цитировали]. Любезнейший, Вы льстите себе, наивно полагая, что от Ваших постов у меня умственные способности стремятся к нулю, гемоглобин в крови понизился & etc. Ваш ход

Странно...Вы себя не отождествляете с программистами, но Вас мои слова видимо задели за живое...Или Вы глубоко сочуствуете кодерам?
Сопереживание это есть гудПризнаю : я Вас сначала недооценил.

Спешу Вас обрадовать: Ваш алгоритм скорее всего неправильный.

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

А теперь давайте рассмотрим пример:

Пусть Ваш рюкзак имеет общий вес 10 кг. И заданы 3 вещи именно в таком порядке: 7кг, 5кг и 5 кг, каждая ценностью по рублю.

Ваш алгоритм выберет оптимум: вещь 7 кг стоимостью в рубль, по той простой причине, что он вещи выбирает по порядку. Хотя правильный ответ, как Вы сами понимаете совсем другой.

Сразу оговорюсь я не знаток Паскаля, и программировал на нем иногда, когда был студентом, но следующие конструкции вызывают подозрение в том, что они могут быть откомпилированы (я могу конечно ошибаться)

w>weight
weight-w,i-1] + v
val[weight-w,i-1] + v

Разве синтаксис Паскаля позволяет складывать массив с целым числом?

Вобщем, я бы посоветовал Вам поуважительней относится к участникам форума, которые без сомнения шарят в теме гораздо больше чем Вы. А решение Вам здесь вряд ли дадут, т.к. здесь не Ваши дружбаны сидят, готовые за Вас впрячься по любому поводу это раз, а во вторых время - это иногда даже больше чем деньги.

ЗЫ. Кстати, код лучше прикладывать аттачем, так как теряется форматирование и становиться труднее читать.

В аттаче глянь блок=схему алгоритма. Следом читалку для блок-схем приаттачу.

Гляделка для блок схем.

2Civic


w[i+1]:=strtoint(memo2.Lines.Strings);


Это просто не может пройти компиляцию. Вы хоть раз это запускали ?

Я понял в чем фишка: обращения к элементам массива в некоторых случаях форумский движок воспринял как теги italic.
Мораль: код нужно прикладывать в аттаче

Кароче понятно..
Чувак перепутал типы данных в Дельфи, даже не потрудился проверить, работает ли программа, алгоритм адназначна неверный, и еще пальцы гнет

Всё компилируется и работает. "Спецы" это еще раз повторю : первоначальный вариант.Рыба так сказать. В аттаче работающий ехе.

2 Лестор
Да,ДАННОЕ решение не позволяет работать с дробными числами и приведенный вами примет так и отработает, но повторю есть второй вариант,который лишен этих недостатков.
З.Ы. Я никого не оскорбляю.

Я понял в чем фишка: обращения к элементам массива в некоторых случаях форумский движок воспринял как теги italic.
Мораль: код нужно прикладывать в аттаче

Видимо так. Прилепил исходник в архиве

Что-то я перемутил с жадным алгоритмом. Код получился шибко длинный, оптимизировать уже лень. ;-)

[code]
(defstruct thing
name
weight
price)

(defun thing-koeff (th)
(/ (thing-price th) (thing-weight th)))

(defstruct bag-problem
max-weight
things
(selected-things nil)
(volume-price 0))

(defparameter *the-problem*
(make-bag-problem
:max-weight 13.5
:things (list (make-thing :name "lamp" :weight 7.5 :price 10)
(make-thing :name "lamp2" :weight 10.5 :price 15)
(make-thing :name "book" :weight 5.5 :price 5)
(make-thing :name "lamp" :weight 5.5 :price 6))))


(defun print-solution (the-problem)
(let ((sel-ths (bag-problem-selected-things the-problem)))
(if sel-ths
(loop for th in (bag-problem-selected-things the-problem) and
idx from 1
summing (thing-weight th) into vol-w
summing (thing-price th) into vol-p
finally (format t "~%Total weight: ~D Total price: ~D~%" vol-w vol-p)
do
(format t "~D. ~D Weight:~D Price:~D Comulative weight:~D~%"
idx (thing-name th) (thing-weight th) (thing-price th) vol-w))
(format t "The solution bag is empty.~%"))))

(defun local-greedy-solution (things selected-things volume-weight volume-price max-weight)
(let ((things-sorted (sort things #'> :key 'thing-koeff))
(things-selected (copy-list selected-things)))
(loop for th in (copy-list things-sorted)
when (

Это что за язык такой?

Это Common Lisp. Пробелы между функциями к сожалению съелись, поэтому код выглядит малость монолитно.

Вроде немного ужалось. На массивах не хочется делать, ибо так симпатичнее IMHO.

[code]
(defstruct thing
name
weight
price)


(defun thing-koeff (th)
(/ (thing-price th) (thing-weight th)))

(defstruct bag-problem
max-weight
things
(selected-things nil)
(volume-price 0))


(defparameter *the-problem*
(make-bag-problem
:max-weight 13.5
:things (list (make-thing :name "lamp" :weight 7.5 :price 10)
(make-thing :name "pen" :weight 10.5 :price 15)
(make-thing :name "book" :weight 5.5 :price 5)
(make-thing :name "paper" :weight 5.5 :price 6))))


(defun print-solution (the-problem)
(let ((sel-ths (bag-problem-selected-things the-problem)))
(if sel-ths
(loop for th in (bag-problem-selected-things the-problem) and
idx from 1
summing (thing-weight th) into vol-w
summing (thing-price th) into vol-p
finally (format t "~%Total weight: ~D Total price: ~D~%" vol-w vol-p)
do
(format t "~D. ~D Weight:~D Price:~D Comulative weight:~D~%"
idx (thing-name th) (thing-weight th) (thing-price th) vol-w))
(format t "The solution bag is empty.~%"))))


(defun greedy-solve (the-problem)
(with-slots (max-weight things selected-things volume-price) the-problem
(setf volume-price 0 selected-things nil)
(let ((l-things (copy-list (sort things #'> :key 'thing-koeff)))
(l-sel-things nil)
(l-vol-price 0)
(l-vol-weight 0)
(l-max-price 0))


(loop while (

А зачем Вы нам рыбу подсунули и потратили наше время на то, чтобы мы разбирались в заведомо неправильном коде?
Там не недостатки, там просто неправильно. Согласитесь смешно звучит: недостатком данной программы является то, что она неправильно работает:))
И почему выложили работающий exe шник (по крайней мере работающий на паре примеров, которые я опробовал), а не работающий код?

Смотрите внимательнее, я еще выложил код от этого ехе. А Ваше время Вас никто не заставлял тратить)))

Я еще раз посмотрел ваши аттачи. Прикреплен код только от "рыбы". Пожалуй Вы правы, не буду я на этот неконструктив с Вами время тратить.