|
buddyroo
|
|
Задача о рюкзаке04.03.2007, 19:33. Показов 70212. Ответов 22
Метки нет (Все метки)
Мне нужно сдать программу на си на задачу о рюкзаке: из n предметов, для которых заданы вес и стоимость, выбрать такие, чтобы суммарный вес был менее 30 кг, а стоимость - наибольшей.
Я нигде в инете не могу найти ее на си...помогите, пожалуйта!! Заранее большое большое спасибо!!! Кристина |
|
| 04.03.2007, 19:33 | |
|
Ответы с готовыми решениями:
22
Задача о рюкзаке Задача о рюкзаке 0-1 Задача о рюкзаке |
|
41 / 41 / 36
Регистрация: 23.11.2006
Сообщений: 153
|
|
| 06.03.2007, 13:03 | |
|
Итак. Прога доволно простая.
0
|
|
|
41 / 41 / 36
Регистрация: 23.11.2006
Сообщений: 153
|
|
| 06.03.2007, 13:05 | |
|
Но Откуда брать данные о предметах?
Можно написать с файлом, в котором содержится информация о предметах: наименовании, стоимости, и весе предмета.
0
|
|
|
41 / 41 / 36
Регистрация: 23.11.2006
Сообщений: 153
|
|
| 06.03.2007, 13:07 | |
|
Попробую сделать, но не факт что завтра будет готова.
Если что, смотри форум после обеда.
0
|
|
|
buddyroo
|
|
| 06.03.2007, 22:03 | |
|
HackSign, спасибо большущее!!!
Да, думаю, можно с файлом. Или со структурой, типо ruksak.ves, ruksak.stoimost и т.д. Но, думаю, ты знаешь лучше!! ![]() Еще раз спасииииииииибо!!! |
|
|
Slayer321
|
|
| 08.12.2007, 21:18 | |
|
Выложите исходник пожалуйста
|
|
|
0 / 0 / 0
Регистрация: 17.11.2007
Сообщений: 51
|
|
| 08.12.2007, 23:24 | |
|
Если поможет для алгоритма, здесь (правда на Delphi) задача с похожей идей:
необходимо загрузить какую либо емкость (допустим рюкзак) с заданной грузоподъемностью 3-мя предметами различного типа с разной ценностью и весом так чтобы общая ценность была максимальной:
0
|
|
|
0 / 0 / 0
Регистрация: 18.12.2007
Сообщений: 3
|
|
| 18.12.2007, 23:15 | |
|
А можно другой исходник?
0
|
|
|
ГостьГГГ
|
||
| 11.12.2008, 10:46 | ||
|
|
||
|
0 / 0 / 0
Регистрация: 17.02.2009
Сообщений: 38
|
|
| 07.04.2010, 20:43 | |
|
доброе время суток! можно кто нить поделиться программой о рюкзаке только на Builder. буду очень благодарна, очень срочно надо!
0
|
|
|
1936 / 1048 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
|
||||||
| 08.04.2010, 10:35 | ||||||
|
в общем как-то так должно быть реализовано (если что - грамматические ошибки исправите сами ;-)):
0
|
||||||
|
0 / 0 / 0
Регистрация: 17.02.2009
Сообщений: 38
|
|
| 08.04.2010, 16:07 | |
|
вы поможете?
0
|
|
|
1936 / 1048 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
|
|
| 09.04.2010, 09:42 | |
|
0
|
|
|
0 / 0 / 0
Регистрация: 17.02.2009
Сообщений: 38
|
|
| 11.04.2010, 21:37 | |
|
спасибо, но мне нужно на buildere!
0
|
|
|
229 / 67 / 11
Регистрация: 02.06.2009
Сообщений: 280
|
|
| 12.04.2010, 14:00 | |
|
Вообще-то это стандартная задача, и, довольно трудная. Решение l_a_m не совсем верное, и работать будет лишь в некоторых случаях.
http://ru.wikipedia.org/wiki/Задача_о_ранце http://en.wikipedia.org/wiki/Knapsack_problem
1
|
|
|
1936 / 1048 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
|
||
| 12.04.2010, 14:19 | ||
|
а по поводу не совсем верного решения - я на абсолютно верное и не претендую ;-) на вскидку написал, если честно то и не компилировал де же ;-) зы: если можно, приведите пример, при котором мой вариант решения, не будет работать :-)
0
|
||
|
229 / 67 / 11
Регистрация: 02.06.2009
Сообщений: 280
|
|
| 12.04.2010, 16:12 | |
|
ну например подход не будет работать когда разница в цене невелика, а в весе существенна.
Возьмем набор - (29,100) (1,99) (1,99) (1,99) (1,99) (1,99)... Жадный алгоритм(который ты юзаеш) всунет предмет с весом 29 цена 100 и один предмет с весом 1 цена 99, а "дороже" - всунуть 30 предметов с весом 1 цена 99. (Для рюкзака с ограничением в 30кг.)
1
|
|
|
1936 / 1048 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
|
|
| 12.04.2010, 17:59 | |
|
хм... логично :-) как-то и не подумал сразу))
спс, за тычок носом ;-)
0
|
|
|
goronkoff
|
|
| 03.06.2010, 21:43 | |
|
У меня курсовая была такая по мат.методам )
Сдал на 5 =) Могу выложить код в Delphi (тогда ещё на нём писАл) если надо кому
|
|
|
0 / 0 / 0
Регистрация: 17.02.2009
Сообщений: 38
|
|
| 04.06.2010, 08:31 | |
|
я буду благодарна, если выложишь)))
0
|
|
| 04.06.2010, 08:31 | |
|
Помогаю со студенческими работами здесь
20
Задача о рюкзаке Задача о рюкзаке 0-1 Задача о рюкзаке
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога
Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
|
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
|
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога
В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
|
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
|
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога
Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
|
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
|
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования.
Часть библиотеки BedvitCOM
Использованы. . .
|
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога
SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
|