Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

RusFAQ.ru: Программирование на языке Pascal


Хостинг Портала RusFAQ.ru:
MosHoster.ru - Профессиональный хостинг на Windows 2008

РАССЫЛКИ ПОРТАЛА RUSFAQ.RU

Чемпионы рейтинга экспертов в этой рассылке

Botsman
Статус: Студент
Рейтинг: 226
∙ повысить рейтинг >>
Micren
Статус: Практикант
Рейтинг: 96
∙ повысить рейтинг >>
Пупорев Юрий Борисович
Статус: Специалист
Рейтинг: 60
∙ повысить рейтинг >>

/ КОМПЬЮТЕРЫ И ПО / Языки программирования / Pascal

Выпуск № 858
от 20.04.2009, 15:35

Администратор:Калашников О.А.
В рассылке:Подписчиков: 251, Экспертов: 45
В номере:Вопросов: 2, Ответов: 2

Нам важно Ваше мнение об этой рассылке.
Оценить этот выпуск рассылки >>

Вопрос № 165009: Здравствуйте! Необходимо решить дискретную задачу о рюкзаке. Вор пробрался на склад, на котором хранится n вещей. Вещь номер i стоит vi денежных единиц и весит wi кг (считаем, что vi и wi - целые числа). Вор хочет украсть товара на максимальную...


Вопрос № 165018: Здравствуйте, мне опять нужна ваша помощь. Задача: В одномерном массиве, состоящем из 10 вещественных элементов вычислить: а) количество отрицательных элементов массива. б) сумму модулей элементов массива, расположенных после минимального по...

Вопрос № 165.009
Здравствуйте!
Необходимо решить дискретную задачу о рюкзаке.
Вор пробрался на склад, на котором хранится n вещей. Вещь номер i стоит vi денежных единиц и весит wi кг (считаем, что vi и wi - целые числа). Вор хочет украсть товара на максимальную сумму, причём максимальный вес, который он может унести в рюкзаке - W (тоже целое число). Что он должен положить в рюкзак?
У меня есть рекурсивное решение этой задачи, но т. к. у этого способа высокая сложность (экспоненциальная), то необходимо решить эту задачу используя динамическое программирование.
Отправлен: 15.04.2009, 08:30
Вопрос задал: Proce (статус: 2-й класс)
Всего ответов: 1
Мини-форум вопроса >>> (сообщений: 0)

Отвечает: Тимошенко Дмитрий
Здравствуйте, Proce!

Я тут прикинул, а что если попробовать такой алгоритм:
Для всех вещей рассчитать стоимость за 1 кг vi/wi. Затем упорядочить получившийся массив с ценами по возрастанию. А потом в цикле добавлять вещи в рюкзак начиная с первых и до полного заполнения рюкзака, или окончания массива. Если цена вещей совпадает - то предпочтение отдаем той, которая меньше весит. (Это можно учесть на этапе сортировки массива с ценами).
Математического обоснования корректности у меня нет (давно это было, уже все позабывал), но интуитивно кажется, что он должен работать правильно.

С уважением, Дмитрий
Ответ отправил: Тимошенко Дмитрий (статус: 5-й класс)
Ответ отправлен: 16.04.2009, 08:34

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 247614 на номер 1151 (Россия) | Еще номера >>
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вопрос № 165.018
    Здравствуйте, мне опять нужна ваша помощь. Задача:
    В одномерном массиве, состоящем из 10 вещественных элементов вычислить:
    а) количество отрицательных элементов массива.
    б) сумму модулей элементов массива, расположенных после минимального по модулю элемента.
    Спасибо за помощь.
    Отправлен: 15.04.2009, 09:25
    Вопрос задал: Ложкин Иван Дмитриевич (статус: Посетитель)
    Всего ответов: 1
    Мини-форум вопроса >>> (сообщений: 0)

    Отвечает: Proce
    Здравствуйте, Ложкин Иван Дмитриевич!
    Код в приложении.

    Приложение:

    Ответ отправил: Proce (статус: 2-й класс)
    Ответ отправлен: 15.04.2009, 11:07

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 247554 на номер 1151 (Россия) | Еще номера >>
  • Отправить WebMoney:
  • Вам помогли? Пожалуйста, поблагодарите эксперта за это!


    Вы имеете возможность оценить этот выпуск рассылки.
    Нам очень важно Ваше мнение!
    Оценить этот выпуск рассылки >>

    Отправить вопрос экспертам этой рассылки

    Приложение (если необходимо):

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

    Обратите внимание!
    Вопрос будет отправлен всем экспертам данной рассылки!

    Для того, чтобы отправить вопрос выбранным экспертам этой рассылки или
    экспертам другой рассылки портала RusFAQ.ru, зайдите непосредственно на RusFAQ.ru.


    Форма НЕ работает в почтовых программах The BAT! и MS Outlook (кроме версии 2003+)!
    Чтобы отправить вопрос, откройте это письмо в браузере или зайдите на сайт RusFAQ.ru.

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)

    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров >>

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.


    © 2001-2009, Портал RusFAQ.ru, Россия, Москва.
    Авторское право: ООО "Мастер-Эксперт Про"
    Техподдержка портала, тел.: +7 (926) 535-23-31
    Хостинг: "Московский хостер"
    Поддержка: "Московский дизайнер"
    Авторские права | Реклама на портале

    ∙ Версия системы: 5.13 от 01.12.2008

    Яндекс Rambler's Top100
    RusFAQ.ru | MosHoster.ru | MosDesigner.ru
    RusIRC.ru | Kalashnikoff.ru | RadioLeader.ru

    В избранное