| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Помогите решить задачу плиз. [D7, XP]
Andrey__ © (2006-11-23 06:50:00)Добрый день Мастера ! Помогите мне пожалуйста решить одну задачу, от этого зависит мое дальнейшее обучение в колледже. Сам пробовал, друзей просил, в форумах ,
но никто не смог помочь.
Задача такая: Есть база товаров, где идет наименование товара и цена.
Пример:
1) Куртка - 800
2) Туфли - 400
3) Туфли - 400
4) Сапоги - 500
5) Куртка (жен) - 800
6) Шуба - 1000
Их нужно сгруппировать так, чтобы сумма не превышала 2000 тенге.
В нашем случае это будет выглядеть так:
1-ая группа
1) Туфли - 400
2) Сапоги - 500
3) Шуба - 1000
(итог: 1900)
2-ая группа
1) Куртка - 800
2) Куртка (жен) - 800
3) Туфли - 400
(Итог: 2000)
В условиях задачи, количество товаров может быть неограниченно. Товаров дороже 2000 рублей нет.
Заранее благодарен !
TUser (2006-12-02 10:33:00) [1]> Твой метод не идеален.
Нет, он дает оптимальное решение рюкзака. Это даже можно доказать.
Andrey__ (2006-12-02 10:19:00) [2]Мастера, плииз у меня есть эти документации но времени в обрез, голова еще не варит, плиз если у кого заволялось подобное, будьте добры.
Alx2 (2006-12-02 10:15:00) [3]>Andrey__ (02.12.06 10:10) [22]
Насчет исходника - плохая идея.
Посмотрите здесь. Возможно, есть пример.
http://algolist.manual.ru/maths/combinat/index.php
Andrey__ (2006-12-02 10:10:00) [4]2 Alx2
Честное слово уже 3-й час в инет кафе найти не могу
"Собственно, это уже писали" не погли бы вы подкинуть ссылку где можно скачать исходник, плиз ?
Alx2 (2006-12-02 10:08:00) [5]Да, после того как написал - прочел условие.
Для неограниченного количества - уже стоит думать о методе ветвей и границ. Собственно, это уже писали
Alx2 (2006-12-02 10:01:00) [6]>Andrey__ (02.12.06 09:24) [19]
Я бы начал вот с чего:
Пусть у всех предметов есть пометка 0 или 1.
1 - входит. 0 - не входит.
Нам подходят наборы, составленные из 0 и 1 такие, что сумма цен на предметы с единицей вписывается в ограничение. В задачке у вас 6 предметов. Потому количество всех вариантов будет 2^6 = 64. Так как их очень мало, то осталось лишь все перебрать (а это цикл от 0 то 63) и выбрать нужное.
for Code := 0 to 63 do
if SumOfPrices(Code)<=Limit then
PrintGroup(Code);
SumOfPrices - суммирует цены предметов у которых стоит единичка на соответствующем месте в Code (в его двоичном представлении)
PrintGroup - печатает предметы у которых стоит единичка на соответствующем месте в Code (в его двоичном представлении)
Andrey__ (2006-12-02 09:24:00) [7]Добрый день Мастера ! Помогите пожалуйста мне до вечера нужно решить эту задачу, а тот пример на паскале который я нашел в сети глючит не подетский. Пожалуйста если у вас есть примеры на паскале или Дельфи, дайте пожалуйста ссылку или на E-mail очень прошу. Все та же задача с суммами.
Думкин (2006-11-23 11:57:00) [8]А я все-таки не понмаю какую задачу решают. Задача так и не сформулирована.
На мой вопрос последовал ответ: "Да..."
А почему не "Нет"?
Anatoly Podgoretsky (2006-11-23 11:42:00) [9]Вспомним условие - экзамен и ни каких подсказок.
А ты что через графы собираешь эту задачу решать.
Задача рюкзака - это дворовое название комбинаторики (накомбинировать набор элементов_.
novill (2006-11-23 11:13:00) [10]> [15] Anatoly Podgoretsky © (23.11.06 11:05)
> Метод бы вспомнить не смог, разработал бы свой. Это же обычная
> комбинаторика.
Это знатное извращение задачу о рюкзаке решать через комбинаторику, хотя если больше ничего не вспоминеатся - то можно :)
Anatoly Podgoretsky (2006-11-23 11:05:00) [11]> from AF (23.11.2006 10:22:13) [13]
Метод бы вспомнить не смог, разработал бы свой. Это же обычная комбинаторика.
Elen (2006-11-23 10:45:00) [12]
> Твой метод не идеален
Чем же?
> В колледже... Считаешь слишком легкой ?
За моими плечами колледж - и я знаю что в таких заведениях дают. Да это задачка из разряда простых. Наши давали и по круче
from AF (2006-11-23 10:22:00) [13]
> Anatoly Podgoretsky
Не сказал бы, что задача легкая. Представь, что ты на экзамене где нет шпаргалок и записок. Смог бы ты сделать эту задачу, тем неменее вспомнить метод Кнапсака или еще кого нибудь))))?
Big Joe_ (2006-11-23 10:17:00) [14]пока сумма не достигнет заданного предела.
хе хе хе... А если она вообще не достигнет заданного предела,так как это получилось в первой группе, что тогда?
Anatoly Podgoretsky (2006-11-23 10:16:00) [15]> Andrey__ (23.11.2006 10:12:10) [10]
> В колледже... Считаешь слишком легкой ?
Естесвенно, он загнул, не мог Гарвард так низко пасть.
Andrey__ (2006-11-23 10:12:00) [16]2 Elen
Твой метод не идеален.
> P.S. В каком это Гарварде такие задачки на прием абитуриентам даю?т
В колледже... Считаешь слишком легкой ?
Elen (2006-11-23 08:12:00) [17]
> Andrey__
Не вижу проблемы - селект с ордером по возрастанию для цен и в цикле выбираеш первые несколько пока сумма не достигнет заданного предела.
P.S. В каком это Гарварде такие задачки на прием абитуриентам даю?т
Andrey__ (2006-11-23 07:46:00) [18]2 MBo
Спасибо, кажись то, что надо. // задача о рюкзаке (knapsack)
MBo (2006-11-23 07:37:00) [19]ищи:
задача о рюкзаке (knapsack)
метод ветвей и границ
перебор с возвратом (backtracking)
subset sum problem
Andrey__ (2006-11-23 07:29:00) [20]2 Думкин
Да...
| |
Страницы: 