Помогите решить задачу плиз.

← →
Andrey__ (2006-11-23 06:50) [0]

Добрый день Мастера ! Помогите мне пожалуйста решить одну задачу, от этого зависит мое дальнейшее обучение в колледже. Сам пробовал, друзей просил, в форумах ,
но никто не смог помочь.
Задача такая: Есть база товаров, где идет наименование товара и цена.

Пример:

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 рублей нет.
Заранее благодарен !

← →
Andrey__ (2006-11-23 06:51) [1]

Нужно написать программу которая могла бы идеально группировать товары.

← →
Думкин © (2006-11-23 07:09) [2]

Очень просто.
Сколько товаров - столько и групп.

← →
Andrey__ (2006-11-23 07:12) [3]

2 Думкин

Нет, товары нужно максимально сгруппировать то есть максимально приблизить к 2000 руб.

← →
Думкин © (2006-11-23 07:24) [4]

> Andrey__ (23.11.06 07:12) [3]

Целевая функция какая?

← →
from AF (2006-11-23 07:27) [5]

Тут тебе не программист а математик наверное нужен, чтобы составить алгоритм.

← →
Andrey__ (2006-11-23 07:29) [6]

2 Думкин

Да...

← →
MBo © (2006-11-23 07:37) [7]

ищи:
задача о рюкзаке (knapsack)
метод ветвей и границ
перебор с возвратом (backtracking)
subset sum problem

← →
Andrey__ (2006-11-23 07:46) [8]

2 MBo

Спасибо, кажись то, что надо. // задача о рюкзаке (knapsack)

← →
Elen © (2006-11-23 08:12) [9]

> Andrey__

Не вижу проблемы - селект с ордером по возрастанию для цен и в цикле выбираеш первые несколько пока сумма не достигнет заданного предела.

P.S. В каком это Гарварде такие задачки на прием абитуриентам даю?т

← →
Andrey__ (2006-11-23 10:12) [10]

2 Elen

Твой метод не идеален.

> P.S. В каком это Гарварде такие задачки на прием абитуриентам даю?т

В колледже... Считаешь слишком легкой ?

← →
Anatoly Podgoretsky © (2006-11-23 10:16) [11]

> Andrey__ (23.11.2006 10:12:10) [10]

> В колледже... Считаешь слишком легкой ?

Естесвенно, он загнул, не мог Гарвард так низко пасть.

← →
Big Joe_ (2006-11-23 10:17) [12]

пока сумма не достигнет заданного предела.

хе хе хе... А если она вообще не достигнет заданного предела,так как это получилось в первой группе, что тогда?

← →
from AF (2006-11-23 10:22) [13]

> Anatoly Podgoretsky

Не сказал бы, что задача легкая. Представь, что ты на экзамене где нет шпаргалок и записок. Смог бы ты сделать эту задачу, тем неменее вспомнить метод Кнапсака или еще кого нибудь))))?

← →
Elen © (2006-11-23 10:45) [14]

> Твой метод не идеален

Чем же?

> В колледже... Считаешь слишком легкой ?

За моими плечами колледж - и я знаю что в таких заведениях дают. Да это задачка из разряда простых. Наши давали и по круче

← →
Anatoly Podgoretsky © (2006-11-23 11:05) [15]

> from AF (23.11.2006 10:22:13) [13]

Метод бы вспомнить не смог, разработал бы свой. Это же обычная комбинаторика.

← →
novill © (2006-11-23 11:13) [16]

> [15] Anatoly Podgoretsky © (23.11.06 11:05)
> Метод бы вспомнить не смог, разработал бы свой. Это же обычная
> комбинаторика.

Это знатное извращение задачу о рюкзаке решать через комбинаторику, хотя если больше ничего не вспоминеатся - то можно :)

← →
Anatoly Podgoretsky © (2006-11-23 11:42) [17]

Вспомним условие - экзамен и ни каких подсказок.
А ты что через графы собираешь эту задачу решать.
Задача рюкзака - это дворовое название комбинаторики (накомбинировать набор элементов_.

А я все-таки не понмаю какую задачу решают. Задача так и не сформулирована.

На мой вопрос последовал ответ: "Да..."

А почему не "Нет"?

← →
Andrey__ (2006-12-02 09:24) [19]

Добрый день Мастера ! Помогите пожалуйста мне до вечера нужно решить эту задачу, а тот пример на паскале который я нашел в сети глючит не подетский. Пожалуйста если у вас есть примеры на паскале или Дельфи, дайте пожалуйста ссылку или на E-mail очень прошу. Все та же задача с суммами.

>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 10:10) [22]

2 Alx2

Честное слово уже 3-й час в инет кафе найти не могу
"Собственно, это уже писали" не погли бы вы подкинуть ссылку где можно скачать исходник, плиз ?

>Andrey__ (02.12.06 10:10) [22]

Насчет исходника - плохая идея.
Посмотрите здесь. Возможно, есть пример.

http://algolist.manual.ru/maths/combinat/index.php

← →
Andrey__ (2006-12-02 10:19) [24]

Мастера, плииз у меня есть эти документации но времени в обрез, голова еще не варит, плиз если у кого заволялось подобное, будьте добры.

> Твой метод не идеален.

Нет, он дает оптимальное решение рюкзака. Это даже можно доказать.

Помогите решить задачу плиз. Найти похожие ветки