Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 07.10.2010, 21:25
Новичок

Отправить личное сообщение для adokS Посмотреть профиль Найти все сообщения от adokS
 
Регистрация: 07.10.2010
Адрес: Тула-ла-ла
Сообщений: 4

Задача о продавце, покупателе и монетах
Задача выглядит так: " у продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец"

Решение есть на этом же сайте -> http://algolist.manual.ru/maths/combinat/payment1.php#1
Возникают некоторые вопросы по этому решению, например, там есть такой абзац:
"Пусть достоинства монет 1=c0, c1, ..., cm-1. Любую сумму вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, где все ki, i=0..2m-1 неотрицательны, которые мы будем кодировать мономами x0^{k0}x1^{k1}...x2m-1^{k2m-1}." Что именны мы здесь кодируем мономами? k0-k2m-1? или саму сумму? или вообще достоинства монет?
__________________
АРБАДАКАРБА
  #2  
Старый 08.10.2010, 02:15
гость

 
Сообщений: n/a

Сообщение от adokS Посмотреть сообщение
Задача выглядит так: " у продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец"
Можно решить динамическим программированием, если n небольшое, скажем, несколько миллионов.

Цитата:
Решение есть на этом же сайте -> http://algolist.manual.ru/maths/combinat/payment1.php#1
Возникают некоторые вопросы по этому решению, например, там есть такой абзац:
"Пусть достоинства монет 1=c0, c1, ..., cm-1. Любую сумму вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, где все ki, i=0..2m-1 неотрицательны, которые мы будем кодировать мономами x0^{k0}x1^{k1}...x2m-1^{k2m-1}." Что именны мы здесь кодируем мономами? k0-k2m-1? или саму сумму? или вообще достоинства монет?
Да все эти базисы шмазисы от лукавого, IMHO... Если алгоритм нормальный, почему бы автору не опубликовать его в приличном peer-reviewed месте, каком нибудь j of combinatorics... а так хрен его поймешь, правильный он или нет
  #3  
Старый 08.10.2010, 14:34
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Сообщение от adokS Посмотреть сообщение
"Пусть достоинства монет 1=c0, c1, ..., cm-1. Любую сумму вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, где все ki, i=0..2m-1 неотрицательны, которые мы будем кодировать мономами x0^{k0}x1^{k1}...x2m-1^{k2m-1}." Что именны мы здесь кодируем мономами? k0-k2m-1? или саму сумму? или вообще достоинства монет?
Мономами кодируется вектор (k0,k1,k2,...,k(2m-1)).
  #4  
Старый 08.10.2010, 14:38
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Сообщение от гость Посмотреть сообщение
Да все эти базисы шмазисы от лукавого, IMHO... Если алгоритм нормальный, почему бы автору не опубликовать его в приличном peer-reviewed месте, каком нибудь j of combinatorics... а так хрен его поймешь, правильный он или нет
Ну я автор и давайте без наездов. Не опубликовал в "приличном peer-reviewed месте", потому что:
(i) не было такой цели;
(ii) алгоритм не представляет собой прорыва в науке, а всего иллюстрацию хорошо известных вещей.
Так что, могу уверить вас, что алгоритм - правильный (с точностью до багов в реализации).
  #5  
Старый 08.10.2010, 18:59
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Да все эти базисы шмазисы от лукавого, IMHO... Если алгоритм нормальный, почему бы автору не опубликовать его в приличном peer-reviewed месте, каком нибудь j of combinatorics... а так хрен его поймешь, правильный он или нет
Да не, зря ты так. Алгоритм необычный. Не бывает одновременно абсолютно универсального и эффективного метода решения задач. Только я здесь чето-то реально не догоняю ))
Получается, что каждую k мы кодируем 1 мономом x0^{k0}x1^{k1}...x2m-1^{k2m-1} и всего таких мономов будет 2m? Выходит, мы каждую k выражаем через преременные x0...x2m-1 и через остальные k0...k2m-1? Или для k0, например у нас моном x0^{k0}? И еще вот:"Пусть I - идеал, порожденный мономами соответствующими нулевой сумме." - Имеется в виду сумма s? Т.е. у нас есть сумма вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, где каждое k закодировано мономом и мы находим такие мономы, чтобы эта сумма равнялась 0?
P.S. Извиняюсь за глупые вопросы ))
  #6  
Старый 08.10.2010, 19:04
Новичок

Отправить личное сообщение для adokS Посмотреть профиль Найти все сообщения от adokS
 
Регистрация: 07.10.2010
Адрес: Тула-ла-ла
Сообщений: 4

Забыл авторизироваться... То что сверху, это я писал
__________________
АРБАДАКАРБА

Последний раз редактировалось adokS, 08.10.2010 в 19:09.
  #7  
Старый 10.10.2010, 03:38
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Сообщение от гость Посмотреть сообщение
Получается, что каждую k мы кодируем 1 мономом x0^{k0}x1^{k1}...x2m-1^{k2m-1} и всего таких мономов будет 2m?
Если считать, что k=(k_0,k_1,k_2,...,k_{2m-1}), то да - кодируем.
Но общее количество вовсе не обязано быть равным 2m. Откуда это 2m у вас взялось?

Сообщение от гость Посмотреть сообщение
"Пусть I - идеал, порожденный мономами соответствующими нулевой сумме." - Имеется в виду сумма s?
Нет, имеются в виду все нулевые суммы, составленные из данных номиналов монет. Причем, согласно утверждению Утв 1., в качестве начального базиса идеала I можно попросту взять все многочлены вида x_0^{c_i}-x_i и x_1^{c_i}x_{m+i}-1.
То есть, если например, m=4 и c_2=2, то для i=2 получаем многочлены:
x_0^2 - x_2 и x_1^2 x_6 - 1. Для других i - аналогично.

Совокупность всех этих многочленов дает базис идеала I, который затем используется для построения базиса Грёбнера этого идеала.

Значение s же используется уже после построения базиса Грёбнера. А именно осуществляется редукция многочлена x_0^s относительно построенного базиса Грёбнера. И из результата этой редукции затем легко получается решение исходной задачи.

Еще раз отмечу, что базис Грёбнера здесь не зависит от s, а только от заданных номиналов монет. Поэтому построенный базис Грёбнера можно многократно использовать для решения задачи с различными s - это делается очень быстро.
Самая же трудоемкая операция здесь - это построение базиса Грёбнера.

Последний раз редактировалось maxal, 10.10.2010 в 03:42.
  #8  
Старый 10.10.2010, 21:17
Новичок

Отправить личное сообщение для adokS Посмотреть профиль Найти все сообщения от adokS
 
Регистрация: 07.10.2010
Адрес: Тула-ла-ла
Сообщений: 4

Сообщение от maxal
Если считать, что k=(k_0,k_1,k_2,...,k_{2m-1}), то да - кодируем.
Но общее количество вовсе не обязано быть равным 2m. Откуда это 2m у вас взялось?
Я сначала не так понял, думал, что, например, k0 кодируем одним мономом, k1-вторым и т.д. до k(2m-1) - вот откуда 2m ))
Получается, что мы выбираем все суммы вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, равные нулю и для каждой из этих сумм у нас свой моном?
А почему мы редуцируем именно многочлен x_0^s? Понимаю, что вопрос довольно объемный, но хотя бы вкратце, если не сложно ))
__________________
АРБАДАКАРБА
  #9  
Старый 11.10.2010, 02:37
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Сообщение от adokS Посмотреть сообщение
Получается, что мы выбираем все суммы вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, равные нулю и для каждой из этих сумм у нас свой моном?
Этих сумм вообще бесконечное число, и соответствующие им мономы образуют (бесконечный) идеал I. Мы же работаем с конечным *базисом* этого идеала. Сначала строим базис из полиномов, указанных в Утв. 1. А затем по нему уже находим базис Грёбнера.
Сообщение от adokS Посмотреть сообщение
А почему мы редуцируем именно многочлен x_0^s?
Потому что x_0 соответствует c_0=1, и моном x_0^s кодирует сумму c_0*s = s.
  #10  
Старый 11.10.2010, 16:51
Новичок

Отправить личное сообщение для adokS Посмотреть профиль Найти все сообщения от adokS
 
Регистрация: 07.10.2010
Адрес: Тула-ла-ла
Сообщений: 4

Теперь все понятно Большое спасибо, что помогли разобраться с алгоритмом. Думаю, мне повезло, что именно вы мне ответили )
__________________
АРБАДАКАРБА
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра