−5°C
завтра: 1°C
Погода в Перми
−5°C
вечером−2°C
ночью−5°C
завтра1°C
Подробно
 92,26
−0.3291
Курс USD ЦБ РФна 29 марта
92,2628
−0.3291
 99,71
−0.5647
Курс EUR ЦБ РФна 29 марта
99,7057
−0.5647
  • Срочно нужна реализация решения задачи о рюкзаке.Желательно в исходных кодах на дельфи. Текст задачи : Имеется набор предметов различного веса и стоимости.Определить группу предметов максимальной общей стоимости,если общий вес рюкзака не должен превышать заданного значения. Дайте ссылочку или код.

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

  • Очередной хитрозадый студент :ха-ха!: :спок:?

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

  • А что за ВУЗ :спок: ?

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

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

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

    Nissan Presage, U-30, KA24DE, 00г.
    Nissan Lafesta, 10г.

  • В ответ на: Ну вообще-то главная задача в программировании, научить вас грамотно составлять алгоритмы.
    Что кстати не плохо надо уметь делать гуманитариям типа - юристы, экономисты и т.д.

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

    Nissan Presage, U-30, KA24DE, 00г.
    Nissan Lafesta, 10г.

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

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

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

    Осторожнее с травой!
    Если хапнешь много дряни
    Увезут тебя с собой
    Злые инопланетяне

  • В ответ на: программа готова,причем моими силами.Правда пришлось посидеть над книгами
    :respect:
    Твои труды даром не пропадут. Поверь :спок:

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

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

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

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

    Слово не воробей, с воза упало и топором не вырубишь...

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

    Слово не воробей, с воза упало и топором не вырубишь...

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

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

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

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

  • Мха-ха-ха-ха! Красиво звоните, по риторике наверное 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

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

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

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

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

    Nissan Presage, U-30, KA24DE, 00г.
    Nissan Lafesta, 10г.

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

    Nissan Presage, U-30, KA24DE, 00г.
    Nissan Lafesta, 10г.

  • В ответ на: здесь не Ваши дружбаны сидят, готовые за Вас впрячься по любому поводу это раз, а во вторых время - это иногда даже больше чем деньги.
    :live:

    Toyota Vitz 2005 1.3-> Mercedes CLK 2002 2.3 Kompressor-> Kia Sportage 2012 Biturbo T-GDI

  • 2Civic


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


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

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

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

    Осторожнее с травой!
    Если хапнешь много дряни
    Увезут тебя с собой
    Злые инопланетяне

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

  • 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 шник (по крайней мере работающий на паре примеров, которые я опробовал), а не работающий код?

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

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

Записей на странице:

Перейти в форум

Модератор: